研究平面图以及其他禁止子图结构，与各种计数问题的结构结合所带来性质和算法，可能涉及到参数计数复杂性。
研究Lovasz局部引理及其应用，包括在近似计数问题方面的应用。
思考一点著名问题，如矩阵乘法算法、四色定理，后者与平面图的张量网络计数问题有弱联系。
预期成果
以上三个研究方向，预期每个方向的研究成果，形成高水平论文一到两篇。预期和学生以及其他同行，合作一些或已列或没列在研究内容之中研究，形成若干论文。
争取有一个二分定理结果，能达到在整个世纪的专业著作中，凡是提及算法和计算复杂性的时候，就应该介绍这样一个起到字典工具书功能的人类目前阶段的终极计算复杂性二分定理结果；可预期，成果中有二分定理，起到了帮助证明这种终极二分定理的作用。
软件研究所中长期发展规划
2016年杰出青年人才发展专项计划入选者
姓名
夏盟佶
工作部门
计算机科学国家重点实验室
资助类别
基础研究
资助编号
ISCAS2016-JQ02
资助金额
Hale Waihona Puke 165万元支持周期2017年1月至2021年12月
研究方向
算法与计算复杂性
研究内容
研究布尔定义域的最一般的Holant问题的计算复杂性，发现其复杂性二分定理，可能需要几个作为中间步骤的弱一点的二分定理。从已有的二分定理证明长度，以及同行未能解决此问题的年头，预期总证明量相当大。