AI基础研究具身智能 AI金融

本网站上的内容仅供参考，不提供医疗或其他专业建议，不代表活水快报、贡献者或合作伙伴的观点。

© 2024-2025 活水快报 - 42Digest.

|

京ICP备2024044642号-15

计算复杂性研究快报

相关分类

计算机科学

Computer Science

人工智能

Artificial Intelligence

计算与语言

Computation and Language

计算复杂性

Computational Complexity

计算机科学

Computer Science

人工智能

Artificial Intelligence

计算与语言

Computation and Language

计算复杂性

Computational Complexity

最新研究

将QMA与QCMA分离为经典神谕

我们构建了一个经典的神谕,证明在相对化的设置中,由具有量子见证(QMA)的高效量子验证器可决定的语言集严格大于那些只能访问经典见证(QCMA)的可决定语言。我们构建的分离经典神谕是对于我们硬币光谱固有的一个决策问题 - 神谕描述了布尔超立方体的两个子集,计算任务是决定是否存在一个量子态,其标准基础测量分布在一个子集上得到了很好的支持,而其傅里叶基础测量分布在其他子集上得到了很好的支持。这相当于估计通过成员资格查询可以访问的两个集合之间的“Forrelation”矩阵的光谱规范。我们的下界源于一个简单的观察,即具有经典见证的查询算法可以多次运行,从分布中生成许多样本,而量子见证是“一次使用”的对象。该观察结果使我们能够减少证明QCMA下界,以证明采样硬度结果不会同时证明QMA下限。为了证明QCMA的采样硬度结果,我们观察到,通过用玻色子表达问题,可以压缩对神谕的量子访问 - 压缩神谕技术的新“第二次量化”视角,这可能是独立的兴趣。利用这种对采样问题的压缩视角,我们证明了采样硬度结果,完成了证明。

量子物理学计算复杂性

用于 QBF 的半代数证明系统

我们为量化布尔公式(QBF)引入了新的半代数证明系统,类似于Nullstellensatz,Shereali-Adams和Sum-of-Squares的命题系统。我们从QBF文献(策略提取)和命题证明复杂性(大小度关系和伪期望)转移到这种设置技术。我们获得许多强大的QBF下界和这些系统之间的分离,即使无视命题硬度。

计算机科学中的逻辑计算复杂性逻辑学

SAT的测量驱动量子算法:通过光谱间隙和测量并行实现性能保证

布尔的可满足性问题(SAT)在理论和实践上都很重要。然而,量子算法的大多数可证明的保证完全依赖于Grover类型的方法,这种方法仅在二次加速时限制了可能的优势,因此寻找超越这种二次障碍的方法成为关键挑战。从这个角度来看,这项工作对最近推出的测量驱动的量子SAT求解器进行了严格的最坏情况运行时分析。重要的是,这种量子算法并不完全依赖于Grover类型的方法,并且显示出有希望的数值性能。我们的分析确定,该算法的运行时取决于两个关键属性之间的指数权衡:相关Hamiltonian的光谱间隙和驾驶测量的成功概率。我们表明,这种取舍可以通过可调的旋转角度系统地控制。除了建立最坏情况的运行时表达式外,这项工作还有助于显著的算法改进。首先,我们开发一个新的读出例程序,即使对于具有多个令人满意的作业的实例,也能有效地找到解决方案。其次,引入了基于完美哈希家族的测量并行化方案。第三,我们建立了测量驱动算法的振幅放大版本。最后,我们展示了框架的实用功能:通过适当调度算法的参数,我们表明它的运行时在一个特殊的SAT实例上从指数级到多项式崩溃,这与它们已知的经典可操作性一致。我们打开的一个问题是在光谱间隙上建立一个非平凡的下界,作为旋转角的函数。解决这个问题直接转化为改进的最坏情况的运行时,有可能实现超象量子优势。

量子物理学计算复杂性

关于冻结边界路径的自动自动网络的复杂性

自动网络是一个实体图,每个实体从有限集合中持有一个状态,并根据本地更新规则进行演变,该规则仅取决于网络图中的邻居。如果状态上有一个命令,即任何节点的状态演变在任何轨道上都是不减少的,那么它就是冻结。它们通常用于模拟流行病传播,扩散现象,如bootstrap percolation或cristal生长。以前的作品已经确定,在网络图是边界树幅的假设下,单个节点的跟踪规范可以捕获的许多问题承认高效的算法。在本文中,我们研究了一个边界路径边界网络更受限制的情况,并显示了两个硬度结果,这些结果在某种程度上说明了在如此强大的图形约束下冻结动力学的复杂性。首先,我们表明跟踪规范检查问题是 NL 完全的。其次,我们表明,决定具有可到达性谓词增强的轨道的第一顺序属性是NP-hard。

计算复杂性离散数学

计算复杂性中的随机排列

Bennett和Gill(1981)的古典结果表明,概率1,P^A≠ ≠ NP^A相对于随机神谕A,概率1,P^π≠ NP^π∩ coNP^π相对于随机排列π。 P^A = NP^A ∩ coNP^A 相对于随机神谕 A 是否保持开放。虽然随机神谕分离已经扩展到特定的单个随机神谕 - 例如Martin-Löf随机或资源绑定的随机神谕 - 没有类似的结果以单独随机排列而闻名。我们引入了一个新的资源边界度量框架,用于分析单个随机排列。我们定义了排列马廷格尔和排列投注游戏,这些游戏表征了排列空间中的测量零集,从而实现了资源绑定随机排列的正式定义。我们的主要结果表明,P^π≠ NP^π∩ coNP^π对于每个多项式时间投注游戏随机排列π。这是相对于单个随机排列的第一个分离结果,而不是几乎无处不在的分离。我们还通过显示每个多项式空间随机排列π的NP^π∩ coNP^π⊈BQP^π来加强Bennett,Bernstein,Brassard和Vazirani(1997)的量子分离。我们研究随机排列和随机神谕之间的关系。我们证明随机神谕是从随机排列中可还原的多项式时间。相反,每个随机排列是否从随机神谕中还原,仍然打开。我们表明,如果 NP ∩ coNP 不是 EXP 的可测量子集,那么 P^A ≠ NP^A ∩ coNP^A 相对于随机神谕 A 的概率为 1。相反,用有时间限制的测量建立这种随机神谕分离意味着BPP是EXP的0子集。

计算复杂性

仅通过Word Counting从正面示例中学习DFA

从积极的例子中学习有限自动机最近获得了关注,作为理解,解释,分析和验证黑盒系统的强大方法。仅仅关注积极的例子的动机源于实际的限制,即我们只能观察一个系统能够做什么(积极的例子),而不是它不能做什么(消极的例子)。与自20世纪70年代以来已知是NP完全的被动DFA学习的被动和消极例子的经典问题不同,仅从积极的例子中学习DFA的主题仍然知之甚少。本文通过利用计算接受单词数的概念来介绍这个问题的新视角,以仔细确定的长度。我们的贡献是双重的。首先,我们证明计算接受所有正面示例的给定大小的DFA所接受的最小单词数是NP-complete,因此仅从正面示例中学习是计算要求很高的。其次,我们提出了一种新的学习算法,具有更好的渐近运行时,这是现有算法中最著名的绑定。虽然我们的实验评估表明,这种算法表现不佳,但它显示出作为增强现有方法的预处理步骤的巨大潜力。

计算复杂性

高维度上与模型无关的超分辨率

超级分辨率的问题,大致上,是重建一个未知的信号到高精度,给定(潜在的嘈杂)信息关于其低度傅里叶系数。超分辨率的先前结果对信号施加了强烈的建模假设,通常要求它是空间分离点源的线性组合。在这项工作中,我们分析了超分辨率问题的一个非常通用的版本,通过考虑d维托 [0,1^d; 雷斯上的完全通用信号,我们不认为点源之间的任何空间分离,甚至该信号是点源的有限线性组合。我们获得两组结果,对应于重建的两个自然概念。 - 在Wasserstein距离进行重建:我们在截止频率T和噪声的大小κ上提供基本匹配的上下边界,在Wasserstein距离中精确重建是可能的。粗略地说,我们在这里的结果表明,对于d维信号,估计≈exp(d)许多傅里叶系数是必要的,并且足以在Wasserstein距离下进行准确的重建。 - “重击者”重建:对于非负信号(等效,概率分布),我们引入了“重击者”重建的新概念,基本上相当于实现分布中所有“足够密集”区域的高精度重建。在这里,我们也在截止频率T和噪声的大小κ上提供基本匹配的上下边界,以便进行准确的重建。我们的结果表明,与Wasserstein重建形成鲜明对比的是,仅对许多傅里叶系数的准确估计是必要的,并且足以用于重击者重建。

数据结构与算法计算复杂性统计理论

测试嘈杂的稀疏性低度多项式

我们考虑测试一个未知的低度多项式p over R^n 是否稀疏而不是稀疏的问题,因为随机选择的点上可以访问多项式p的嘈杂评估。这是经典问题与噪声学习稀疏低度多项式上的问题的属性测试类比,将Chen,De和Servedio(2020)的工作从嘈杂的线性函数扩展到一般低度多项式。我们的主要结果给出了低度多项式稀疏测试何时允许独立于维度的恒定样本复杂性的精确表征,以及该机制中匹配的恒定样本算法。对于任何均值-零,方差-一有限支持的分布X在实数上,度d和任何sparsity参数s ≤ T,我们定义一个可计算函数MSG_X,d(?),并且:对于T ≥MSG_X,d(s),我们给出一个O_s,X,d(1)-sample算法,区分一个多线性度-d多项式在R^上与p-s-s。(x) + noise)_x∼X^⊗ n。至关重要的是,样品的复杂性完全独立于环境维度n。 - 对于T ≤MSG_X,d(s) - 1,我们表明即使没有噪声,任何给定的样本(x,p(x))_x∼X^⊗ n也必须使用Ω_X,d,s(log n)示例。我们的技术采用了Dinur等人的结果的概括。 (2007年)在傅立德函数的傅里叶尾部,而不是 {0,1}^n 广泛的有限支持分布,这可能是独立的。

数据结构与算法计算复杂性

追踪 AG 代码:走向满足吉尔伯特-瓦尔沙莫夫边界

编码理论中最古老的问题之一是将Gilbert-Varshamov与显式二进制代码绑定。在更大但仍然是恒定大小的领域,代数几何代码已知可以击败GV绑定。在这项工作中,我们利用这种现象,获取 AG 代码的痕迹。我们的希望是,AG代码超过GV绑定的余量将承受从恒定的字段扩展到二进制字段的跟踪所产生的参数损失。与通常的字母减少方法concatenation相反,我们对AG(TAG)代码的跟踪分析使用AG代码的代数结构 - 包括在字母减少步骤中。我们的主要技术贡献是一个适合分析TAG代码的Hasse-Weil型定理。经典定理(及其Grothendieck微量公式扩展)在这种设置中是不充分的。虽然我们没有得到改进的构造,但我们表明,不断强化我们的界限就足够了。我们还分析了TAG代码在我们约束下的局限性,并证明在高距离制度中,它们不如代码连接。我们的 Hasse-Weil 型定理比分析 TAG 代码所需的要广泛得多。特别是,我们对指数金额得出新的估计。

信息论计算复杂性代数几何

计算复杂性受限的6G波形光谱效率分析

在这项工作中,我们介绍了如何在无线波形的频谱效率(SE)分析中解释信号处理的计算时间复杂度的教程。我们的方法在实现更高的SE需要复杂性的惩罚的情况下特别相关,这是6G候选波形中存在的常见权衡。我们认为SE来自数据速率,该速率受到时间依赖的开销的影响。因此,忽视SE分析中的计算复杂性开销为更计算复杂的波形带来了不公平的优势,因为它们需要更大的计算资源来满足符号期以下的信号处理运行时。我们用两个案例研究展示了我们的观点。首先,我们从文献中引用符合IEEE 802.11a的基础带处理器,以表明它们的运行时显着影响了上层感知的SE。在第二个案例研究中,我们表明,如果提供等效的高性能计算资源,在SE方面被认为效率较低的波形可以超越其计算成本更高的对应物。基于这些案例,我们相信我们的教程可以解决在不同计算资源约束下运行的波形的比较SE分析。

信号处理计算复杂性性能

珍珠因果等级中可满足性可性网关

Pearl的因果层次结构(PCH)是一个关于概率,介入和反事实陈述的推理的中心框架,然而PCH公式的可满足性问题在几乎所有经典设置中都是难以计算的。我们通过参数化复杂性的镜头重新审视这一挑战,并确定牵引力的第一批网关。我们的结果包括固定参数和XP算法,用于关键概率和反事实片段的可满足性,使用原始树幅和变量数等参数,以及匹配的硬度结果,映射可牵引力的极限。从技术上讲,我们偏离了通常用于基于树幅的算法的动态编程范式,而是利用良好形成的因果模型的结构表征,为因果推理提供了新的算法工具包。

人工智能计算复杂性

高维多指数模型中弱学习能力的基本计算极限

多索引模型 - 函数仅依赖于其投影在子空间上的非线性变换 - 是使用神经网络研究特征学习的有用基准。本文研究了本假设类中高效可学习性的理论边界,侧重于用一阶迭代算法弱恢复其低维结构所需的最小样本复杂性,在高维方案中,样本 n=α d 的数量与协方差维度 d 成正比。我们的发现分为三部分:(i)我们确定在哪些条件下,可以通过任何 α>0; (ii) 单序算法的单步学习一个微不足道的子空间,如果琐碎子空间是空的,我们为一个简单的子空间的存在提供了必要和充分的条件,其中只能在某个样本复杂度 α>α_c 之上学习方向,其中α_c标记了计算阶段的过渡。在一组有限但有趣的真正困难的方向 - 类似于平价问题 - α_c被发现存在差异。最后,(iii)我们表明,不同方向之间的相互作用会导致复杂的分层学习现象,当耦合到更容易时,可以依次学习方向。我们详细讨论了与这些功能相关的大楼梯图片(并将其与原始楼梯进行比较)。我们的理论建立在一阶迭代方法中近似消息传递的最优性之上,在广泛的算法中划定了基本的可学习性极限,包括受过梯度下降训练的神经网络,我们在此背景下进行了讨论。

机器学习无序系统与神经网络计算复杂性

图形类在自我交集下关闭

图形类是单调的,如果它在取子图下关闭。众所周知,由有限许多障碍物定义的单调类具有边界,如果并且只有当其中一个障碍物是所谓的三脚架时,即具有完全相同一个度3和路径的树的不连接结合。这种二分法也正好描述了许多NP-硬算法问题承认多项式时间算法的那些单调的图形类。然而,这些算法二分法并没有扩展到所有遗传类的宇宙,这些类是在诱导子图下关闭的类。这就引出了一个自然的问题,即我们是否可以将单调类的已知算法二分法扩展到更大的遗传类家族。我们对这个问题给出了一个肯定的答案,通过考虑在自我交集下关闭的世袭图类的家庭,众所周知,这些类严格位于单调和遗传类之间。我们证明了在不包括三脚架的自我交集封闭类中图形的新结构特征。我们使用我们的表征来给出最大独立集的完整二分法,以及由有限许多障碍物定义的自截封闭类的加权变体:如果类排除三脚架和NP-hard否则,这些问题在P中。这在最大独立设置上推广了几个已知结果。我们还使用它来获取由有限许多障碍物定义的双部分图形的自截闭类的最大诱导匹配的二分法。同样,我们获得由有限许多障碍物定义的自截闭类(双部分)事件图的可满足性和计数的二分法,以及有限许多障碍物定义的自截闭式图的斜宽的界限。

组合数学计算复杂性离散数学数据结构与算法

讨厌的噪音真的比恶意噪音更难吗?

我们考虑了计算效率算法在噪声存在下学习的相对能力和局限性,在两个研究良好且具有挑战性的对抗性噪声模型下用于学习布尔函数:恶意噪声,其中对手可以任意损坏给学习者的示例的随机子集;以及讨厌的噪声,其中对手可以任意损坏给学习者的示例的对抗性选择子集。我们考虑独立于分布和固定分布的设置。我们的主要结果突出了这两种设置之间的巨大差异:对于独立于分布的学习,我们证明了两种噪声模型之间的强烈等价性:如果一个类函数在η速率恶意噪声的存在下可以有效地学习,那么它在η速率讨厌噪声的存在下也可以有效地学习。与此形成鲜明对比的是,对于固定分发设置,我们显示了一个任意大分离:在标准加密假设下,对于任何任意大值r,存在一个概念类,其中多项式时间学习算法可以容忍的恶意噪声速率η_恶意与此类学习算法可以容忍的恶劣噪声的速率η_nasty之间存在r的比例。为了抵消固定分布设置的负结果,我们定义了一个广泛而自然的算法类别,即那些忽略矛盾示例(ICE)的算法。我们表明,对于这些算法,恶意噪声和讨厌的噪声在噪声率中相当于两个因素:任何使用η速率恶意噪声成功的高效ICE学习者都可以转换为具有η/2速率讨厌噪声的高效学习者。我们进一步证明,上述两个因素是必要的,再次在一个标准的加密假设下。

机器学习计算复杂性数据结构与算法

搜索与搜索崩溃的选举控制类型

选举控制类型是试图通过改变选举结果的方式改变选举结果[BTT92]。我们说两个兼容的(即具有相同的输入类型)控制类型,即与相同的选举系统E形成崩溃的对,如果对于每个可能的输入(通常由候选人集,投票集,焦点候选人,有时与未遂更改的性质相关的其他参数)可以成功执行,无论是还是两者都不能成功进行。对于Hemaspaandra,Hemaspaandra和Menton[HHM20]发现的七名将军(即举行所有选举制度)中的每一对选举控制类型崩溃对,以及Carleton等人发现的每一对额外的选举控制类型崩溃对。 [CCH+24)对于否决权和批准(以及许多其他选举制度,根据该文件定理3.6和3.9),坍塌对的成员具有相同的复杂性,因为它们是相同的集合。然而,具有相同的复杂性(如集合)不足以保证作为搜索问题,它们具有相同的复杂性。在本文中,我们探讨了崩溃对的搜索版本之间的关系。对于Hemaspaandra,Hemaspaandra和Menton [HHM20]和Carleton等人的崩溃对。 [CCH+24],我们证明这对成员的搜索版本的复杂性是多项式相关的(给定的访问,对于赢家问题本身不在多项式时间的情况下,到获胜者问题的神谕)。除此之外,我们提供高效的减少,从解决方案到计算解决方案到另一个解决方案。对于具体的系统多元化,否决权和批准,我们完全确定它们的哪个(由于我们的结果)多项式相关的崩溃搜索-问题对是多项式时间可计算的,哪些是NP-硬的。

计算机科学与博弈论计算复杂性多智能体系统

冷凝和提取对抗在线对抗

我们研究从在线非遗忘符号修复(oNOSF)源进行确定性压缩和提取的任务,这是一种有缺陷的随机性的自然模型,在许多参数机制中不可能提取[AORSV, EUROCRYPT'20]。 (g,l)-oNOSF源是l块的序列,其中至少g块是好的(独立的,有最小熵),剩下的坏块由在线对手控制,并且可以任意与先前的块相关。以前,[CGR,FOCS'24]证明不可能在g≤0.5 l时凝结超过速率1/2,并且显示当g≥0.51l和n在l中呈指数时,冷凝器的存在。在这项工作中,我们不仅构建了第一个与[CGR,FOCS'24]的存在结果相匹配的显式冷凝器,而且当g≥0.51l和n在l中仅多对数时,我们通过处理情况进行双指数改进。我们还获得了改进的显式结构,用于将低熵oNOSF源转换为均匀的oNOSF源。接下来,我们通过显示冷凝器的存在来解决oNOSF源冷凝器的存在问题,即使n是一个足够大的常数并且l正在增长(前提是g≥0.51l)。我们将冷凝器应用于集体硬币翻转和集体采样,广泛研究容错分布式计算中的问题,并为它们提供非常简单的协议。最后,我们研究从oNOSF来源提取的可能性。对于下界,我们引入了在线影响的概念——扩展了布尔函数的影响概念——并建立了严格的界限,这意味着提取下限。我们还通过领导者选举协议构建显式提取器,这些协议击败了标准弹性函数[AL,Combinatorica'93]。

计算复杂性

来自考夫曼-奥本海姆综合体的低灵敏度直接产品测试器和五氯苯酚

我们研究考夫曼-奥本海姆式复合体(STOC 2018,Eur。 J。梳。 2023年),具有基本和强烈的明确描述。在回答考夫曼、奥本海姆和温伯格(STOC 2025)的公开问题时,我们表明他们支持低声条件下稀疏的直接产品测试仪。我们的证明依赖于Bafna-Minzer和Dikstein-Dinur(均为STOC 2024)协议测试的HDX表征,这是Kaufman等人的最新结果,并遵循Bafna-Lifshitz-Minzer和Dikstein-Dinur-Lbotzky(均为FOCS 2024)的技术。最终,任务减少到显示KO复合体的某些二维子组的维度无关的共聚扩展;遵循考夫曼和奥本海姆的“Dehn方法”(ICALP 2021),我们通过在多项式环上为某些矩阵组建立高效的演示边界来做到这一点。正如Bafna,Minzer和Vyas(STOC 2025)所示,我们的直接产品测试结果的结果是,考夫曼-奥本海姆复合物也可用于获得具有任意小常数和准线性长度的五氯苯酚。因此,在构建这些五氯苯酚时可以使用复杂的数论和代数组理论工具。

计算复杂性

蒙纳迪奇和受保护的二订单逻辑的数据日志可表达性

我们描述了Monadic二阶逻辑(MSO)中的句子,这些句子在存在鹅卵石游戏中等同于Datalog程序的有限结构。我们还表明,对于可以在MSO中表达并在同态下关闭的每个类有限结构的C类,对于所有整数l,k,在Feder和Verdi的意义上存在一个规范的宽度(l,k)数据程序Pi。相同的特征也适用于受保护的二阶逻辑(GSO),它正确地扩展了MSO。为了证明我们的结果,我们表明GSO中的每一个C类,其补充在同态下是约束满意度问题(CSP)的有限结合,可数分类结构。众所周知,MSO和Datalog的交集包含嵌套monadically定义查询(Nemodeq)的类;同样,我们表明GSO和Datalog的交集包含所有可以通过嵌套保护查询的更富有表现力的语言表达的问题。然而,通过利用我们的结果,我们可以证明这两种查询语言都不能作为表征,因为我们在MSO和Datalog的交叉中展示了一个在嵌套保护查询中无法表达的查询。

计算机科学中的逻辑计算复杂性逻辑学

fruit-SALAD:一种风格对齐的艺术作品数据集,以揭示图像嵌入中的相似性感知

视觉相似性的概念对于计算机视觉以及围绕图像的矢量嵌入的应用程序和研究至关重要。然而,基准数据集的稀缺性在探索这些模型如何看待相似性方面构成了重大障碍。在这里,我们介绍了Style Aligned Artwork Datasets(SALADs),以及一个水果-SALAD的例子,有10,000张水果描绘的图像。这个组合的语义类别和风格基准包括10个易于识别的水果类别中的100个实例,跨越10个易于区分的风格。利用生成图像合成的系统管道,这个视觉上多样化但平衡的基准展示了各种计算模型中语义类别和风格相似性权重的显着差异,包括机器学习模型,特征提取算法和复杂性度量,以及概念模型以供参考。这个精心设计的数据集提供了一个控制和平衡的平台,用于比较分析相似性感知。 SALAD框架允许比较这些模型如何执行语义类别和样式识别任务,以超越轶事知识的水平,使其具有可量化和定性可解释性。

计算机视觉与模式识别人工智能计算复杂性机器学习

PCF Learned Sort：一种具有O(n loglog n)期望复杂度的学习增强排序算法

排序是计算机科学中最基础的算法之一。近年来，使用机器学习提升排序速度的Learned Sort引起了广泛关注。虽然现有研究表明Learned Sort在实证上比经典排序算法更快，但它们并未提供关于其计算复杂度的理论保证。我们提出了分段常数函数（PCF）Learned Sort，一种具有理论保证的Learned Sort算法。我们证明了在对数据分布进行温和假设的前提下，PCF Learned Sort的期望复杂度为𝒪(n loglog n)。我们还在合成数据集和真实数据集上实证确认了PCF Learned Sort具有𝒪(n loglog n)的计算复杂度。这是首个从理论上支持Learned Sort实证成功的研究，并为解释Learned Sort为何快速提供了证据。代码可在https://github.com/atsukisato/PCF_Learned_Sort获取。

数据结构与算法计算复杂性

继续滚动加载更多