|  |
演讲简介
Given a fixed pattern P, we consider the problem of determining whether a graph contains a subgraph isomorphic to P. This is one of the most basic NP-complete problems that includes Clique and Hamiltonian Cycle as special cases.
AC0 is an important class of restricted Boolean circuits. AC0 circuits have constant-depth, polynomial size, and consist of AND, OR, NOT gates. We are interested in the AC0 complexity of this problem, determined by the smallest possible exponent $C(P)$ for which this problem possesses circuits of size $n^{C(P)+o(1)}$.
For the "colorful" version, where the target graph G is V(P)-colored, we prove an almost tight lower bound that coincides with the treewidth of the pattern $P$ up to a logarithmic factor. For the average-case version, where the target graph is an Erdős–Rényi random graph, we give a characterization of $C_ave(P)$ in purely combinatorial terms up to a multiplicative factor of 2. We give some evidence suggesting that the colorful version of the problem is better structured than the standard (worst-case, uncolored) one.
Based on joint work with Alexander Razborov and Benjamin Rossman.
