【2021.12.20】On the AC0 Complexity of Subgraph Isomorphism-子图同构问题的AC0电路复杂性

报告题目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.

地址: 中国 上海市杨浦区淞沪路2005号复旦大学江湾校区2号交叉学科楼
邮编: 200438
电话: +86-21-31242153
传真: +86-21-31242153
E-mail: dataology@fudan.edu.cn