Math @ Duke

Publications [#350209] of Benjamin Rossman
Papers Published
 Rossman, B, Lower bounds for subgraph isomorphism,
Proceedings of the International Congress of Mathematicians, Icm 2018, vol. 4
(January, 2018),
pp. 34433464, ISBN 9789813272934
(last updated on 2022/05/21)
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 NC1 vs. L. We give an overview of unconditional averagecase lower bounds for this problem (and its colored variant) in a few important restricted classes of Boolean circuits.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

