研究了基于决策可分离负范式电路的布尔函数主要子句的枚举问题 EnumIP,将其归纳于枚举复杂度的框架内,并证明它在 OutputP 与 IncP 中。此外,研究了两个更具挑战性的限制问题,其中一个是关于表示部分最小诱导解释的子句的问题,另一个则涉及到了可解释人工智能领域中的重要概念 - 具有合理原因的主要子句,最后还提供了一些可行性证据。
Jan, 2023
本文旨在从参数化复杂度的角度,探究枚举计算复杂度和算法问题,首先定义了不同的枚举概念,然后运用不同算法,例如核函数和自减技术,从而得到参数有效的枚举算法,并且通过核函数的概念,对固定参数极易枚举的问题进行了表述。
Jun, 2013
本文采用伪维度来表征量子电路的表达能力,并证明了量子电路输出概率分布的伪维度上界多项式上界,由此证明了已知多项式尺寸和深度的量子电路是可 PAC 学习的一个电路输出状态类中至少有一个状态具有指数级状态复杂度。
Feb, 2020
研究基于电路复杂度的先验模型,并使用它们来学习部分信息中的布尔函数。该模型假设,布尔函数或布尔字符串由一些电路的贝叶斯混合生成。在电路复杂度方面表现良好。
Jun, 2023
本文提供了一种形式基础,可以在其中比较 AC 的变体,从而使它们的各种属性的作用和语义更加透明。本文还为 AC 提供了新的结果,包括具有和没有确定性的 AC 之间的指数分离;完备性和不完备性结果;以及计算最可能的解释时 (MPEs) 的可处理性结果(或缺乏处理性结果)。
Aug, 2017
本文提出了一个简单,强大和灵活的机器学习框架,用于减少计算困难的集合问题的枚举变量搜索空间,并通过输入分布产生的信息提示来增强现有的最先进的求解器。我们将我们的框架实例化为图中列出所有最大团的问题,这是网络分析,数据挖掘和计算生物学中的中心问题。我们证明了我们的方法在具有数百万个顶点和边的真实世界网络上的实用性,不仅保留了所有最优解,而且还积极剪枝输入实例大小,导致比最先进的算法快几倍。最后,我们探讨了我们提出的框架的可扩展性和鲁棒性的限制,表明监督学习在实践中应用于 NP-hard 问题是可行的。
Feb, 2019
提出了一种线性时间延迟算法,用于枚举由 Meek 和 Chickering 规则产生的马尔可夫等价类中的有向无环图,并在实验中评估其有效性,同时向马尔可夫等价本身提供了新的见解。
本文探究图中支配集问题,将其多项式约化为超图中的极小转移序列问题。研究了在一些图结构中的解决方案,尝试寻找该问题的输出多项式时间算法。
Jul, 2014
概率电路、多线性多项式、边缘推断、多项式语义和二元分布是该研究论文的五个关键词,论文证明了对于二元分布来说,这些概率电路模型在一定意义上等价,而且研究了一个称为概率生成电路的多项式语义在分类随机变量上的自然扩展,结果证明边缘推断变得 #P 难。
Feb, 2024
研究枚举的可压缩性及其在可计算可枚举集合相对 Kolmogorov 复杂度方面的作用,并针对压缩的强和弱形式研究其增益,证明了任何可计算可枚举集合都具有强压缩和无增益弱压缩,并研究一种位置游戏以深入理解强无增益压缩。
Apr, 2023