夏盟佶 男 博导 中国科学院软件研究所
电子邮件： mingji 
ios.ac.cn
通信地址： 中科院软件所 计算机科学实验室
邮政编码： 100190
研究领域
计数复杂性、张量网络
招生信息
招生专业
招生方向
教育背景
工作经历
2011-10~2013-10,德国马普信息研究所, 博士后
2009-05~2018-09,中国科学院软件研究所, 助理研究员、副研究员
2008-08~2009-04,美国威斯康星大学, 研究助理
两组二分定理参考文献
对已知的二分定理推广，无论是推广定义域，还是值域，还是函数形式，例如从对称函数到一般函数，还是函数集合的形式，例如从单点集到一般集合，还是问题框架，例如从#CSP问题到Holant问题，虽然很少公开在论文中被问到，都是明显的未解决问题。
我对正在指导的前两篇博士论文，提出了文献方面的具体要求——尽量完整地分别整理出一般图与平面图的布尔定义域的计数问题的二分定理文献。
一、一般图上布尔定义域的计数二分定理
#CSP
1. Creignou N, Hermann M. Complexity of Generalized Satisfiability Counting Problems[J/OL]. Information and computation, 1996, 125(1): 1-12. https://doi.org/10.1006/inco.1996.0016.
0-1值域
2. Dyer M, Goldberg L A, Jerrum M. The Complexity of Weighted Boolean #CSP [J/OL]. SIAM Journal on Computing, 2009, 38(5): 1970-1986. https://doi.org/10.1137/070690201.
非负有理数值域
3. Bulatov A, Dyer M, Goldberg L A, et al. The complexity of weighted Boolean #CSP with mixed signs [J/OL]. Theoretical Computer Science, 2009, 410(38-40): 3949-3961. https: //doi.org/10.1016/j.tcs.2009.06.003.
有理数值域
4. Cai J Y, Lu P, Xia M. The complexity of complex weighted Boolean #CSP [J/OL]. Journal of Computer and System Sciences, 2014, 80(1): 217-236. https://doi.org/10.1016/j.jcss.2013. 07.003.
复数值域
Holant^*和Holant^c
1. Cai J Y, Lu P, Xia M. Holant problems and counting CSP [C/OL]//STOC ’09: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2009: 715–724. https://doi.org/10.1145/1536414.1536511.
复数值域对称Holant^*和实数值域对称Holant^c
2. Cai J Y, Lu P, Xia M. Dichotomy for Holant* Problems of Boolean Domain [C/OL]// Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011: 1714-1728. https://doi.org/10.1137/1.9781611973082.132.
复数值域Holant^*
3. Cai J Y, Huang S, Lu P. From Holant to #CSP and Back: Dichotomy for Holant^c Problems [J/OL]. Algorithmica, 2012, 64: 511-533. https://doi.org/10.1007/s00453-012-9626-6.
复数值域对称Holant^c
4. Cai J Y, Lu P, Xia M. Dichotomy for Real Holant^c Problems [C/OL]//Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2018: 1802-1821. https://doi.org/10.1137/1.9781611975031.118.
实数值域Holant^c
5. Backens M. A complete dichotomy for complex-valued Holant^c [C/OL]//45th Interna- tional Colloquium on Automata, Languages, and Programming (ICALP 2018): volume 107. Schloss Dagstuhl – Leibniz-Zentrum fur Informatik, 2018: 12:1-12:14. https://doi.org/10. 4230/LIPIcs.ICALP.2018.12.
复数值域Holant^c
Holant
1. Lin J, Wang H. The Complexity of Boolean Holant Problems with Nonnegative Weights[J/OL]. SIAM Journal on Computing, 2018, 47(3): 798-828. https://doi.org/10.1137/17M113304X.
非负实数值域
2. Huang S, Lu P. A Dichotomy for Real Weighted Holant Problems [J/OL]. Computational Complexity, 2016, 25: 255-304. https://doi.org/10.1007/s00037-015-0118-3.
实数值域对称Holant
3. Shao S, Cai J Y. A Dichotomy for Real Boolean Holant Problems [C/OL]//2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2020: 1091-1102. https://doi.org/10.1109/FOCS46700.2020.00105.
实数值域
4. Cai J Y, Guo H, Williams T. A complete dichotomy rises from the capture of vanishing signatures [C/OL]//Proceedings of the forty-fifth annual ACM symposium on Theory of com- puting. Association for Computing Machinery, 2013: 635-644. https://doi.org/10.1145/ 2488608.2488687.
复数值域对称Holant
5. Cai J Y, Fu Z, Guo H, et al. A Holant Dichotomy: Is the FKT Algorithm Universal? [C/OL]// 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015: 1259-1276. https://doi.org/10.1109/FOCS.2015.81.
复数值域对称Holant
以上信息来自2017级研究生博士论文
二、平面图以及其他禁图子式图类上布尔定义域的计数二分定理
（待续）
以上信息来自2020级研究生博士论文