报告题目：On the AC0 Complexity of Subgraph Isomorphism-子图同构问题的AC0电路复杂性
主讲嘉宾：李元
报告时间：2021年12月20日 13：30-15：30
报告地点：复旦大学江湾校区交叉二号楼 E1006室
报告摘要：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.
关于嘉宾：Yuan Li is currently a software engineer in Google. He earned his BSc in computer science from Fudan University in 2011, and his PhD in computer science from the University of Chicago in 2017. His PhD research is in circuit complexity. He has also worked on complex orthogonal design, and cryptographic Boolean function analysis. He has published papers in conferences and journals such as IEEE Transactions on Information Theory, FOCS, SIAM Journal on Computing, and Cryptography and Communications.