计算复杂性

2025年05月 的作者和标题

[51] arXiv:2505.10445 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 关于具有几何局部相互作用的经典线性动力学的量子计算复杂性：去量子化和普遍性 显示英文标题

标题： On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

Kazuki Sakamoto, Keisuke Fujii

评论： 32页，5图

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)

[52] arXiv:2505.11395 (交叉列表自 math.RA) [中文pdf, pdf, html, 其他]

标题： 保守Maltsev约束满足问题 显示英文标题

标题： Conservative Maltsev Constraint Satisfaction Problems

Manuel Bodirsky, Andrew Moorhead

评论： 68页，12幅图

主题： 环与代数 (math.RA) ; 计算复杂性 (cs.CC)

[53] arXiv:2505.12954 (交叉列表自 cs.SI) [中文pdf, pdf, html, 其他]

标题： 大小为$k$的图元计数在局部差分隐私下的应用 显示英文标题

标题： Counting Graphlets of Size $k$ under Local Differential Privacy

Vorapong Suppakitpaisarn, Donlapark Ponnoprat, Nicha Hirankarn, Quentin Hillebrand

评论： 本文已被AISTATS 2025接受。 https://proceedings.mlr.press/v258/suppakitpaisarn25a.html

主题： 社会与信息网络 (cs.SI) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS)

[54] arXiv:2505.13749 (交叉列表自 cs.FL) [中文pdf, pdf, html, 其他]

标题： 一种关于带有一个计数器的自动机中半线性目标集的复杂度二分法 显示英文标题

标题： A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter

Yousef Shakiba, Henry Sinclair-Banks, Georg Zetzsche

评论： 32页；已接受用于LICS 2025

主题： 形式语言与自动机理论 (cs.FL) ; 计算复杂性 (cs.CC) ; 计算机科学中的逻辑 (cs.LO)

[55] arXiv:2505.14061 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 线性哈希是最优的 显示英文标题

标题： Linear Hashing Is Optimal

Michael Jaber, Vinayak M. Kumar, David Zuckerman

评论： 20页，1图；将发表于STOC 2025

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[56] arXiv:2505.14691 (交叉列表自 cs.LO) [中文pdf, pdf, html, 其他]

标题： 伽罗瓦能量博弈：解决各种定量可达性问题 显示英文标题

标题： Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems

Caroline Lemke, Benjamin Bisping

评论： 提交至CONCUR 2025

主题： 计算机科学中的逻辑 (cs.LO) ; 计算复杂性 (cs.CC)

[57] arXiv:2505.14840 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 任意温度下注意力的次二次算法和难度 显示英文标题

标题： Subquadratic Algorithms and Hardness for Attention with Any Temperature

Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye

评论： 34页，2图，摘要已缩短以符合arXiv要求

主题： 机器学习 (cs.LG) ; 计算复杂性 (cs.CC)

[58] arXiv:2505.15359 (交叉列表自 cs.LO) [中文pdf, pdf, 其他]

标题： 群论逻辑 显示英文标题

标题： Group Order Logic

Anatole Dahan

主题： 计算机科学中的逻辑 (cs.LO) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 群论 (math.GR)

[59] arXiv:2505.15905 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 有容量的公平范围聚类：难解性与近似算法 显示英文标题

标题： Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms

Ameet Gadekar, Suhas Thejaswi

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[60] arXiv:2505.16457 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 具有和不具有共享纠缠的量子通信复杂度的最大分离 显示英文标题

标题： Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement

Atsuya Hasegawa, François Le Gall, Augusto Modanese

评论： 14页；v2：修正了拼写错误并进行了小的编辑。

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)

[61] arXiv:2505.17993 (交叉列表自 math.CO) [中文pdf, pdf, 其他]

标题： 寻找爪型图中的d-割集 显示英文标题

标题： Finding d-Cuts in Claw-free Graphs

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, Siani Smith

主题： 组合数学 (math.CO) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM)

[62] arXiv:2505.18895 (交叉列表自 stat.ML) [中文pdf, pdf, html, 其他]

标题： 边际公平：风险衡量下的公平决策 显示英文标题

标题： Marginal Fairness: Fair Decision-Making under Risk Measures

Fei Huang, Silvana M. Pesenti

主题： 机器学习 (stat.ML) ; 计算复杂性 (cs.CC) ; 计算机与社会 (cs.CY) ; 机器学习 (cs.LG) ; 风险管理 (q-fin.RM)

[63] arXiv:2505.18948 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： Transformer模型的精确表达能力与填充 显示英文标题

标题： Exact Expressive Power of Transformers with Padding

William Merrill, Ashish Sabharwal

评论： NeurIPS 2025

主题： 机器学习 (cs.LG) ; 计算复杂性 (cs.CC) ; 形式语言与自动机理论 (cs.FL)

[64] arXiv:2505.20069 (交叉列表自 cs.LO) [中文pdf, pdf, 其他]

标题： 通过独立性在DQBF中的改进扩展变量 显示英文标题

标题： Better Extension Variables in DQBF via Independence

Leroy Chew, Tomáš Peitl

主题： 计算机科学中的逻辑 (cs.LO) ; 计算复杂性 (cs.CC)

[65] arXiv:2505.20497 (交叉列表自 math.RA) [中文pdf, pdf, html, 其他]

标题： 多项式时间算法针对黑盒可分配扩展群组 显示英文标题

标题： Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups

Mikhail Anokhin

评论： 13页

主题： 环与代数 (math.RA) ; 计算复杂性 (cs.CC) ; 符号计算 (cs.SC)

[66] arXiv:2505.20607 (交叉列表自 math.ST) [中文pdf, pdf, 其他]

标题： 低次硬度对于划分问题的强大性 显示英文标题

标题： Strong Low Degree Hardness for the Number Partitioning Problem

Rushil Mallarapu, Mark Sellke

评论： 使用Typst排版；24页

主题： 统计理论 (math.ST) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 概率 (math.PR)

[67] arXiv:2505.22351 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 探查$d$-割集的$H$-自由图 显示英文标题

标题： Finding $d$-Cuts in Probe $H$-Free Graphs

Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson, Giacomo Paesani, Daniël Paulusma

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 组合数学 (math.CO)

[68] arXiv:2505.22410 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 更快的卷积：重新审视Yates和Strassen 显示英文标题

标题： Faster Convolutions: Yates and Strassen Revisited

Cornelius Brand, Radu Curticapean, Baitian Li, Kevin Pratt

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[69] arXiv:2505.22743 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 通过低次似然的量子学习中的信息-计算差距 显示英文标题

标题： Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

Sitan Chen, Weiyuan Gong, Jonas Haferkamp, Yihui Quek

评论： 88页，2幅图

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 机器学习 (cs.LG)

[70] arXiv:2505.23787 (交叉列表自 math.LO) [中文pdf, pdf, html, 其他]

标题： 卡尔玛初等函数的最小替换基底 显示英文标题

标题： A Minimal Substitution Basis for the Kalmar Elementary Functions

Mihai Prunescu, Lorenzo Sauras-Altuzarra, Joseph M. Shunia

评论： 修订增加了一处引用并提供了细微的澄清

主题： 逻辑 (math.LO) ; 计算复杂性 (cs.CC) ; 计算机科学中的逻辑 (cs.LO)

[71] arXiv:2505.23978 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 如何无条件地验证一个小设备是否是量子的 显示英文标题

标题： How to Verify that a Small Device is Quantum, Unconditionally

Giulio Malavolta, Tamer Mour

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)