Publications [#350209] of Benjamin Rossman

Papers Published

1. Rossman, B, Lower bounds for subgraph isomorphism, Proceedings of the International Congress of Mathematicians Icm 2018, vol. 4 (January, 2018), pp. 3443-3464, ISBN 9789813272934
   (last updated on 2026/01/14)

   Abstract:
   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 NC¹ 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.