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
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
Publication Date
January 1, 2018
Volume
4
Start / End Page
3443 / 3464