AF: Small: Classification Program for Counting Problems
AF: Small: Classification Program for Counting Problems
批准号:
1714275
负责人:
Jin-Yi Cai
金额:
$45.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2017
资助国家:
美国
项目状态:
已结题
起止时间:
2017-09-01 至 2021-08-31
中文摘要
这个项目是对计数问题的计算复杂性的研究。PI的目的是对被称为乘积和计算的问题的复杂性进行分类。这些计数问题来自计算机科学的各个领域,甚至是其他研究领域。它们是自然定义的,包括诸如顶点覆盖、图着色和图匹配等计数问题。在计算复杂性理论中,没有比实现对一大类计算问题的完整分类更高的目标了。这通常是根据P和NP理论来完成的,其中P和NP分别表示可用确定性算法和非确定性算法在多项式时间内计算的问题。人们对PI的分类程序非常感兴趣,特别是全息算法的概念。为了寻找正确的分类公式,还进行了大量的计算实验,提供了一个让本科生参与研究的机会。更清晰地划分什么是有效计算的,什么不是有效计算的,将在计算机科学内外产生更广泛的影响。在CS内部,人工智能方面的大量工作都是围绕着类似的称为配分函数的模型展开的。在计算机科学之外,研究配分函数在统计物理学中有着悠久的传统,这项研究揭示了所谓的精确解模型。更专业地说,这些计算定义为sum_sigma prod_f f|sigma,其中f‘s是局部约束函数,sigma是局部变量的赋值。有三个相关的框架来研究这些问题。(1)自旋系统或图同态,(2)计数CSP问题,(3)Holant问题。在过去的几年里,下列论文获得了相当多的证据:一大类乘积和计算可以精确地分为三类:(I)在P中可计算;(Ii)对于一般图,#P-Hard,但对于平面图,在P中可解;此外,对于自旋系统和计数CSP,范畴(II)正好对应于那些可以用带匹配门的全息算法来解决的问题。但对于Holant问题,还有更多新的可处理的问题类别。PI计划证明适用于非对称约束函数的分类定理。如果对于不对称和对称的约束函数都能解决这个问题,这将是一个统一的结果,回答了至少从卡斯特林在1960年代的S时代起就没有解决的问题。
英文摘要
This project is a study of the computational complexity of counting problems. The PI aims to classify the complexity of problems known as Sum-of-Product computations. These counting problems come from all parts of computer science, and even other fields of study. They are naturally defined and include such counting problems as vertex covers, graph colorings, and graph matchings. There is also a strong connection to problems studied in statistical physics.In computational complexity theory, there is no higher aim than to achieve a complete classification of a wide class of computational problems. This is usually done in terms of the P and NP theory, where P and NP denote problems computable in polynomial time by deterministic and nondeterministic algorithms, respectively. There has been strong interest in the PI's classification program, especially with the concept of holographic algorithms. There is also a significant amount of computational experimentation in the search for the right formulation of the classification, providing an opportunity to engage undergraduate students in research.A sharper delineation between what is or is not efficiently computable will have broader impact within computer science and beyond. Within CS, a substantial body of work in AI is centered around similar models called partition functions. Outside computer science, there is a long tradition in statistical physics to study partition functions, and this study informs the so-called exactly solved models.In more technical terms, these are computations defined as sum_sigma prod_f f | sigma, where the f's are local constraint functions, and the sigmas are assignments to local variables. There are three related frameworks to study these problems.(1) Spin systems or graph homomorphisms,(2) Counting CSP problems, and (3) Holant problems.Over the past several years, the following thesis has gained considerable evidence, namely a large family of Sum-of-Product computations can be classified into exactly three categories with an explicit criterion on the constraint function set:(I) Computable in P;(II) #P-hard for general graphs, but solvable in P for planar graphs; and(III) #P-hard even for planar graphs.Furthermore, for Spin systems and Counting CSP, category (II) corresponds precisely to those problems which can be solved by holographic algorithms with matchgates. But for Holant problems, there are additional novel tractable classes of problems. The PI plans to prove classification theorems that apply to asymmetric constraint functions. If this can be settled for asymmetric as well as symmetric constraint functions, it will be a unifying result, answering questions that are open at least since the time of Kasteleyn in the 1960's.
期刊论文(9)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
11th Innovations in Theoretical Computer Science Conference (ITCS 2020).
第 11 届理论计算机科学创新会议 (ITCS 2020)。
DOI:
--
发表时间:
2020
期刊:
11th Innovations in Theoretical Computer Science Conference (ITCS 2020
影响因子:
--
作者:
[Cai, Jin-Yi, Govorov, Artem]
通讯作者:
Govorov, Artem
DOI:
10.1016/j.ic.2018.01.003
发表时间:
2017-02
期刊:
Inf. Comput.
影响因子:
--
作者:
[Jin-Yi Cai;Zhiguo Fu;Mingji Xia]
通讯作者:
Jin-Yi Cai;Zhiguo Fu;Mingji Xia
DOI:
10.4230/lipics.icalp.2020.66
发表时间:
2020-02
期刊:
ArXiv
影响因子:
--
作者:
[A. Govorov;Jin-Yi Cai;Martin E. Dyer]
通讯作者:
A. Govorov;Jin-Yi Cai;Martin E. Dyer
Holographic algorithms beyond matchgates
超越匹配门的全息算法
DOI:
10.1016/j.ic.2018.01.002
发表时间:
2018
期刊:
Information and Computation
影响因子:
1
作者:
[Cai, Jin-Yi, Guo, Heng, Williams, Tyson]
通讯作者:
Williams, Tyson
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).
第 47 届自动机、语言和编程国际学术研讨会 (ICALP 2020)。
DOI:
--
发表时间:
2020
期刊:
and Programming (ICALP 2020
影响因子:
--
作者:
[Cai, Jin-Yi
Liu]
通讯作者:
Cai, Jin-Yi
Liu
共 7 条
AF: Small: Counting Problems, Holographic Algorithms and Dichotomy Theorems
-
批准号:1217549
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2012
-
负责人:Jin-Yi Cai
-
依托单位:
Counting Problems and Dichotomy Theorems
-
批准号:0914969
-
项目类别:Standard Grant
-
资助金额:$39.73万
-
财政年份:2009
-
负责人:Jin-Yi Cai
-
依托单位:
Holographic Algorithms and Reductions
-
批准号:0830488
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2008
-
负责人:Jin-Yi Cai
-
依托单位:
Some Problems in Complexity Theory
-
批准号:0511679
-
项目类别:Continuing Grant
-
资助金额:$20.0万
-
财政年份:2005
-
负责人:Jin-Yi Cai
-
依托单位:
Some Problems in Structural and Lattice Complexity
-
批准号:0208013
-
项目类别:Standard Grant
-
资助金额:$29.41万
-
财政年份:2002
-
负责人:Jin-Yi Cai
-
依托单位:
Worst-Case v.s. Average-Case Complexity and Applications to Secure Cryptography
-
批准号:0196197
-
项目类别:Standard Grant
-
资助金额:$22.0万
-
财政年份:2000
-
负责人:Jin-Yi Cai
-
依托单位:
Worst-Case v.s. Average-Case Complexity and Applications to Secure Cryptography
-
批准号:9820806
-
项目类别:Standard Grant
-
资助金额:$22.0万
-
财政年份:1999
-
负责人:Jin-Yi Cai
-
依托单位:
Realistic Uncheatable Benchmarks
-
批准号:9634665
-
项目类别:Standard Grant
-
资助金额:$24.22万
-
财政年份:1996
-
负责人:Jin-Yi Cai
-
依托单位:
Uncheatable Benchmarks
-
批准号:9319393
-
项目类别:Continuing Grant
-
资助金额:$13.42万
-
财政年份:1993
-
负责人:Jin-Yi Cai
-
依托单位:
PYI: A Study of Computational Complexity Theory
-
批准号:9496107
-
项目类别:Continuing Grant
-
资助金额:$9.44万
-
财政年份:1993
-
负责人:Jin-Yi Cai
-
依托单位:
PYI: A Study of Computational Complexity Theory
-
批准号:9057486
-
项目类别:Continuing Grant
-
资助金额:$14.4万
-
财政年份:1990
-
负责人:Jin-Yi Cai
-
依托单位:
国内基金
海外基金
登录
查看更多内容
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2024
-
负责人:
-
依托单位:
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
-
批准号:
-
项目类别:省市级项目
-
资助金额:10.0万元
-
批准年份:2022
-
负责人:张祥忠
-
依托单位:
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
-
批准号:32000033
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:林平
-
依托单位:
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
-
批准号:31972324
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2019
-
负责人:高学文
-
依托单位:
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
-
批准号:81900988
-
项目类别:青年科学基金项目
-
资助金额:21.0万元
-
批准年份:2019
-
负责人:毛梦莹
-
依托单位:
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
-
批准号:31870821
-
项目类别:面上项目
-
资助金额:56.0万元
-
批准年份:2018
-
负责人:陈江宁
-
依托单位:
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
-
批准号:31802058
-
项目类别:青年科学基金项目
-
资助金额:26.0万元
-
批准年份:2018
-
负责人:麻慧
-
依托单位:
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
-
批准号:31772128
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2017
-
负责人:吴建国
-
依托单位:
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
-
批准号:81704176
-
项目类别:青年科学基金项目
-
资助金额:20.0万元
-
批准年份:2017
-
负责人:赵继梦
-
依托单位:
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
-
批准号:91640114
-
项目类别:重大研究计划
-
资助金额:85.0万元
-
批准年份:2016
-
负责人:何祖华
-
依托单位: