夏盟佶 男 博导 中国科学院软件研究所
电子邮件： mingji 
ios.ac.cn
通信地址： 中科院软件所 计算机科学实验室
邮政编码： 100190
研究领域
计数复杂性、张量网络
招生信息
招生专业
招生方向
教育背景
工作经历
2011-10~2013-10,德国马普信息研究所, 博士后
2009-05~2018-09,中国科学院软件研究所, 助理研究员、副研究员
2008-08~2009-04,美国威斯康星大学, 研究助理
科研工作与公开问题
部分研究结果恰好与若干同行所问的公开问题相关，列举如下：
1、多重受限的计数问题的计算复杂性问题
同行问：论文The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM J. Comput. 2001 第七节第二段前半段“Even regarding just the problems studied here, several unanswered questions stand out. For one, we have shown that a number of problems are hard in bounded-degree bipartite graphs and constant-degree regular graphs, but we do not know what happens if these conditions are imposed simultaneously. Do these problems remain hard in bipartite k-regular graphs, or even just bipartite regular graphs?”。
我们答：论文#3-Regular Bipartite Planar Vertex Cover is #P-Complete. TAMC 2006 给出了上述提问在#VC计算问题上的回答。对更多计数问题的回答可见Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci. 2007。
2、两比特匹配门的通用性问题与多比特匹配门的群特性问题
同行问1：论文 Quantum Circuits That Can Be Simulated Classically in Polynomial Time. SIAM J. Comput. 2002 第七节第一段“The exact power of matchgate techniques for deriving polynomial time classical algorithms remains to be resolved. Are there indirect methods not yet identified for mapping richer classes computations into matchgates? Can our par-ticular class of polynomially simulatable circuits be extended by allowing in addition arbitrary use of one-bit gates? Do circuits based on k-bit matchgates for k>2 have greater power for encoding computations?”中最后一句问使用k（k>2）比特匹配门的线路，是否有更强大的计算能力。
同行问2：论文 On the Theory of Matchgate Computations. Electron. Colloquium Comput. Complex. 2006 第五节第二段“One structural question remains for the general matchgates. We believe that non-singular 2k by 2k matchgate characters also form a group. The group property is likely to suggest deeper symmetries of these matchgate computations.” 中问一类匹配门矩阵是否构成群。
我们答：论文 A Theory for Valiant's Matchcircuits (Extended Abstract). STACS 2008 否定了第一问，肯定了第二问。
3、全息算法的基塌缩问题
同行问：论文 A collapse theorem for holographic algorithms with matchgates on domain size at most 4. Inf. Comput. 2014 第七节“This paper presents a collapse theorem for holographic algorithms with matchgates on domain size at most 4. The proof technique is mainly judicious applications of MGI. One certainly hopes that the proof can be extended to larger domain sizes. The main obstacle comes from the proof of Theorem 6.1. To prove the 4 × 4 submatrix has full rank, we use MGI to prove its determinant does not vanish. For larger domain sizes, the dimensions of the submatrix would be greater than 4 × 4 and it is not clear how one can use MGI to compute its determinant.”中提到了所用的MGI方法推广到大定义域时有障碍。
同行答：论文Basis collapse for holographic algorithms over all domain sizes. STOC 2016，使用MGI方法，研究了大定义域下的基塌缩问题。
我答：论文 Base collapse of holographic algorithms. STOC 2016，使用初等变换的方法，研究了大定义域下的基塌缩问题。
两份解答是同期的独立研究，都需一些较自然的前提条件，用以得到基塌缩。
4、变量版洛瓦兹局部引理问题
同行问：论文 The Lovász Local Lemma - A Survey. CSR 2013 第三页中有：“Problem: What is the ultimate Condition(G,\bar{p}) for the variable version of LLL?”
我们答：论文 Variable-Version Lovász Local Lemma: Beyond Shearer's Bound. FOCS 2017 给出了一种明确的变量版局部引理的条件。
5、完美匹配计数问题在限制图子式情形下的计算复杂性问题
同行问：论文 Counting the Number of Perfect Matchings in K5-Free Graphs. Theory Comput. Syst. 2016 第六节第二段“After a talk about this result, Michael Saks asked for which minors the count-ing problem for perfect matching remains #P-hard. Observe that the singly-crossing graph H in Fig. 10 has a K5 and a K3,3 as a minor. Hence it is possible to count even on graph classes which are neither K5- nor K3,3-free (but H-free). It is an interesting open question for which minors counting remains #P-hard.”
我们答：论文 Parameterizing the Permanent: Hardness for fixed excluded minors. SOSA 2022 明确回答了此问题。
同行议：然后论文 Killing a vortex. FOCS 2022 第一节第二段指出：“A negative answer to this question was re-cently given by Curticapean and Xia [6], [7] who proved that the classic result of Valiant on the #P-completeness of #P ERFECT MATCHING holds even when restricted to K8-minor free graphs.”
我也问过一些有同行回答的公开问题，列举如下：
1、全息归约逆命题问题
我问：论文Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems. ICALP 2010 中第四节“It is still possible that the converse of the two theorems holds for most situation except some special cases. In the following conjecture, we simply add a condition on the arity, but maybe this is far from the right condition.
Conjecture 1. #F|H and #P|Q are two counting problems, such that at least one of F, H, P, Q contains some function of arity more than 1. If they are result equivalent, then they are algebra equivalent.”
同行答：论文 A Complete Dichotomy Rises from the Capture of Vanishing Signatures. SIAM J. Comput. 2016 中“We note that this is the first counter example involving non-unary signatures in the Boolean domain to the converse of the Holant theorem, which provides a negative answer to a conjecture made by Xia in [37] (Conjecture 4.1).”
两组二分定理参考文献
对已知的二分定理推广，无论是推广定义域，还是值域，还是函数形式，例如从对称函数到一般函数，还是函数集合的形式，例如从单点集到一般集合，还是问题框架，例如从#CSP问题到Holant问题，虽然很少公开在论文中被问到，都是明显的未解决问题。
我对正在指导的前两篇博士论文，提出了文献方面的具体要求——尽量完整地分别整理出一般图与平面图的布尔定义域的计数问题的二分定理文献。
一、一般图上布尔定义域的计数二分定理
（待续）
以上信息来自2017级研究生博士论文
二、平面图以及其他禁图子式图类上布尔定义域的计数二分定理
（待续）
以上信息来自2020级研究生博士论文