Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


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 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 average-case 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 27708-0320