• 讲座信息

12.20 | 【学院讲座】On the AC0 Complexity of Subgraph Isomorphism-子图同构问题的AC0电路复杂性

2021.12.17

演讲者李元
头衔职位谷歌云计算部门软件工程师
时间2021年12月20号下午1:30–3:30
地点江湾校区二号交叉学科楼E1006
联系人阚海斌,hbkan@fudan.edu.cn

演讲简介

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.