计算复杂性

2025年01月 的作者和标题

[1] arXiv:2501.00008 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： 特殊集合覆盖与布尔函数 显示英文标题

标题： Special Coverings of Sets and Boolean Functions

Stepan Margaryan

主题： 计算复杂性 (cs.CC)

[2] arXiv:2501.00831 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 无危险决策树 显示英文标题

标题： Hazard-free Decision Trees

Deepu Benson, Balagopal Komarath, Jayalal Sarma, Nalli Sai Soumya

评论： 31页

主题： 计算复杂性 (cs.CC)

[3] arXiv:2501.02347 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 整数包络的参数化线性公式 显示英文标题

标题： A parameterized linear formulation of the integer hull

Friedrich Eisenbrand, Thomas Rothvoss

主题： 计算复杂性 (cs.CC) ; 优化与控制 (math.OC)

[4] arXiv:2501.02653 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 新的伪随机生成器和使用提取器的相关性界限 显示英文标题

标题： New Pseudorandom Generators and Correlation Bounds Using Extractors

Vinayak M. Kumar

评论： 34页，ITCS 2025

主题： 计算复杂性 (cs.CC)

[5] arXiv:2501.02886 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 局部枚举：非全等情形 显示英文标题

标题： Local Enumeration: The Not-All-Equal Case

Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, Navid Talebanfard

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

[6] arXiv:2501.03281 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 布尔可满足性问题的逆交集 显示英文标题

标题： Inverse Intersections for Boolean Satisfiability Problems

Paul W. Homer

主题： 计算复杂性 (cs.CC)

[7] arXiv:2501.03710 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 关于决策DNNF的限制片段的复杂性 显示英文标题

标题： On complexity of restricted fragments of Decision DNNF

Andrea Calí, Igor Razgon

主题： 计算复杂性 (cs.CC)

[8] arXiv:2501.03871 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： 分段路由的参数化复杂性 显示英文标题

标题： Parameterized Complexity of Segment Routing

Cristina Bazgan, Morgan Chopin, André Nichterlein, Camille Richer

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

[9] arXiv:2501.04224 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 模计数CSP：约简与算法 显示英文标题

标题： Modular Counting CSP: Reductions and Algorithms

Amirhossein Kazeminia, Andrei A.Bulatov

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

[10] arXiv:2501.05638 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： Mim-宽度是paraNP-完全的 显示英文标题

标题： Mim-Width is paraNP-complete

Benjamin Bergougnoux, Édouard Bonnet, Julien Duron

评论： 27页，9图

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

[11] arXiv:2501.06574 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： 列是PSPACE完全的在三角形网格上 显示英文标题

标题： Col is PSPACE-complete on Triangular Grids

Kyle Burke, Craig Tennenhouse

评论： 10页，16图

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

[12] arXiv:2501.07529 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 确定突变树之间的距离和共识 显示英文标题

标题： Determining distances and consensus between mutation trees

Luís Cunha, Jack Kuipers, Thiago Lopes

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

[13] arXiv:2501.07752 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 面向读一次 ACC0 电路的扩展器随机游走的伪随机性 显示英文标题

标题： Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits

Emile Anand

评论： 28页，4图

主题： 计算复杂性 (cs.CC)

[14] arXiv:2501.09545 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： 单调电路的团近似难度 显示英文标题

标题： Hardness of clique approximation for monotone circuits

Jarosław Błasiok, Linus Meierhöfer

主题： 计算复杂性 (cs.CC)

[15] arXiv:2501.11192 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 非交叉$H$图：一种允许FPT算法的适当区间图的推广 显示英文标题

标题： Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms

Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro, Daniël Paulusma

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

[16] arXiv:2501.11683 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 在《Flesh and Blood》中为激进风格策略进行优化是NP难的 显示英文标题

标题： Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard

Leonardo Gasparini Romão, Samuel Plaça de Paula, Eduardo Takeo Ueda

主题： 计算复杂性 (cs.CC)

[17] arXiv:2501.12260 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 非均匀确定性有限自动机在有限代数结构上 显示英文标题

标题： Nonuniform Deterministic Finite Automata over finite algebraic structures

Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski

主题： 计算复杂性 (cs.CC)

[18] arXiv:2501.12282 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： Jelly-No和Hanano游戏在各种约束条件下的复杂性 显示英文标题

标题： Complexity of Jelly-No and Hanano games with various constraints

Owen Crabtree, Valia Mitsou

评论： 37页，44图

主题： 计算复杂性 (cs.CC)

[19] arXiv:2501.12365 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 广义$q$-元函数的稀疏傅里叶变换的高效算法 显示英文标题

标题： Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions

Darin Tsui, Kunal Talreja, Amirali Aghazadeh

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 信息论 (cs.IT) ; 机器学习 (cs.LG)

[20] arXiv:2501.14337 (交叉列表自 cs.CC) [中文pdf, pdf, 其他]

标题： 图上的接近码的交互式预言证明 显示英文标题

标题： Interactive Oracle Proofs of Proximity to Codes on Graphs

Hugo Delavenne (GRACE), Tanguy Medevielle (IRMAR, GRACE), Élina Roussel (GRACE)

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR)

[21] arXiv:2501.14569 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 解释决策问题中相变的普遍性 显示英文标题

标题： Explaining the Ubiquity of Phase Transitions in Decision Problems

Andrew Jackson

主题： 计算复杂性 (cs.CC)

[22] arXiv:2501.00154 (交叉列表自 cs.AI) [中文pdf, pdf, html, 其他]

标题： 线性模型的概率解释 显示英文标题

标题： Probabilistic Explanations for Linear Models

Bernardo Subercaseaux, Marcelo Arenas, Kuldeep S Meel

评论： AAAI论文的扩展版

主题： 人工智能 (cs.AI) ; 计算复杂性 (cs.CC)

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

标题： 诱导小图模型。 II. 诱导小图的多项式时间检测的充分条件 显示英文标题

标题： Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors

Clément Dallard, Maël Dumas, Claire Hilaire, Anthony Perez

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

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

标题： 非结合Lambek演算与经典逻辑的复杂性 显示英文标题

标题： Complexity of Nonassociative Lambek Calculus with classical logic

Paweł Płaczek (WSB Merito University in Poznan, Poland)

评论： 在NCL'24会议论文集中，arXiv:2412.20053

期刊参考： EPTCS 415，2024，第150-164页

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

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

标题： 量子伪随机认证 显示英文标题

标题： Pseudorandom quantum authentication

Tobias Haug, Nikhil Bansal, Wai-Keong Mok, Dax Enshan Koh, Kishor Bharti

评论： 7 + 21页，2幅图

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR)

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

标题： 量子计算的对称性 显示英文标题

标题： Symmetric quantum computation

Davi Castro-Silva, Tom Gur, Sergii Strelchuk

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

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

标题： 实数上的抗碰撞哈希洗牌 显示英文标题

标题： Collision-resistant hash-shuffles on the reals

George Barmpalias, Xiaoyan Zhang

主题： 逻辑 (math.LO) ; 计算复杂性 (cs.CC) ; 信息论 (cs.IT)

[28] arXiv:2501.03698 (交叉列表自 math.OC) [中文pdf, pdf, html, 其他]

标题： 半正规划的平方和逼近计算复杂度 显示英文标题

标题： Computational complexity of sum-of-squares bounds for copositive programs

Marilena Palomba, Lucas Slot, Luis Felipe Vargas, Monaldo Mastrolilli

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC)

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

标题： 由原始作用保留的$S_ω$结构 显示英文标题

标题： Structures preserved by primitive actions of $S_ω$

Manuel Bodirsky, Bertalan Bodor

评论： 22页加上参考文献

主题： 逻辑 (math.LO) ; 计算复杂性 (cs.CC)

[30] arXiv:2501.04151 (交叉列表自 math.OC) [中文pdf, pdf, html, 其他]

标题： 高效利用LP热启动进行约束矩阵的线性修改 显示英文标题

标题： Efficient LP warmstarting for linear modifications of the constraint matrix

Guillaume Derval, Bardhyl Miftari, Damien Ernst, Quentin Louveaux

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC)

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

标题： 电路复杂度界限用于视觉自回归模型 显示英文标题

标题： Circuit Complexity Bounds for Visual Autoregressive Model

Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song

主题： 机器学习 (stat.ML) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC) ; 计算与语言 (cs.CL) ; 机器学习 (cs.LG)

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

标题： 关于计算限制和可证明高效的视觉自回归模型标准：细粒度复杂度分析 显示英文标题

标题： On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis

Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song

主题： 机器学习 (cs.LG) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC) ; 计算机视觉与模式识别 (cs.CV)

[33] arXiv:2501.05259 (交叉列表自 cs.PL) [中文pdf, pdf, 其他]

标题： 带栈的可逆计算与“故障的可逆管理” 显示英文标题

标题： Reversible Computation with Stacks and "Reversible Management of Failures"

Matteo Palazzo, Luca Roversi

评论： 16页，2图

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

[34] arXiv:2501.05283 (交叉列表自 math.GR) [中文pdf, pdf, html, 其他]

标题： 关于具有虚拟阿贝尔目标的同态测试的复杂性 显示英文标题

标题： On the complexity of epimorphism testing with virtually abelian targets

Murray Elder, Jerry Shen, Armin Weiß

评论： 41页，2张表格

主题： 群论 (math.GR) ; 计算复杂性 (cs.CC)

[35] arXiv:2501.06427 (交叉列表自 cond-mat.dis-nn) [中文pdf, pdf, html, 其他]

标题： 自旋玻璃中稳定局部最优的强低次数难解性 显示英文标题

标题： Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

Brice Huang, Mark Sellke

主题： 无序系统与神经网络 (cond-mat.dis-nn) ; 计算复杂性 (cs.CC) ; 数学物理 (math-ph) ; 概率 (math.PR)

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

标题： 图神经网络的计算能力：电路复杂性界限视角 显示英文标题

标题： On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, Jiahao Zhang

主题： 机器学习 (cs.LG) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC)

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

标题： 稳定集多面体的等级$|V(G)|/3$对于 Lovász--Schrijver SDP 算子 显示英文标题

标题： Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator

Yu Hin Au, Levent Tunçel

主题： 组合数学 (math.CO) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 优化与控制 (math.OC)

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

标题： 匹配割和在有界半径和直径的二部图上的变体 显示英文标题

标题： Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter

Felicia Lucke

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

[39] arXiv:2501.08905 (交叉列表自 cs.GT) [中文pdf, pdf, html, 其他]

标题： 计算尊重它们的游戏对称性和均衡解 显示英文标题

标题： Computing Game Symmetries and Equilibria That Respect Them

Emanuel Tewolde, Brian Hu Zhang, Caspar Oesterheld, Tuomas Sandholm, Vincent Conitzer

评论： 长版本和更新版本的已发表论文，发表于第39届人工智能国际学术会议（AAAI 2025）论文集。24页，2图，1表

主题： 计算机科学与博弈论 (cs.GT) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC) ; 多智能体系统 (cs.MA)

[40] arXiv:2501.09828 (交叉列表自 math.OC) [中文pdf, pdf, html, 其他]

标题： 关于p阶锥规划的复杂性 显示英文标题

标题： On the Complexity of p-Order Cone Programs

Víctor Blanco, Victor Magron, Miguel Martínez-Antón

评论： 22页，2张表格

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC)

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

标题： 回答相关问题 显示英文标题

标题： Answering Related Questions

Édouard Bonnet

评论： 19页，2图

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

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

标题： 具有循环变压器的超图神经算法推理 显示英文标题

标题： Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, Zhen Zhuang

主题： 机器学习 (cs.LG) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC) ; 计算与语言 (cs.CL)

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

标题： 量子一阶逻辑捕获对数时间/空间的量子可计算性 显示英文标题

标题： Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability

Tomoyuki Yamakami

评论： （A4，10号字，27页，2张图）这是在《第20届欧洲可计算性会议（CiE 2024）论文集》中发表的扩展摘要的完整修正版，荷兰阿姆斯特丹，2024年7月8日至12日，计算机科学讲义，第14773卷，第311-323页，施普林格出版社，2024年

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 计算机科学中的逻辑 (cs.LO)

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

标题： $O(1)$-多维网格图连通性、EMST和DBSCAN的回合MPC算法 显示英文标题

标题： $O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN

Junhao Gan, Anthony Wirth, Zhuo Zhang

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 计算几何 (cs.CG) ; 分布式、并行与集群计算 (cs.DC)

[45] arXiv:2501.12062 (交叉列表自 cs.DM) [中文pdf, pdf, html, 其他]

标题： 近似无冲突、线性有序和非单色超图着色的复杂度 显示英文标题

标题： Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Živný

评论： 包含 arXiv:2205.14719

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

[46] arXiv:2501.12293 (交叉列表自 cs.IT) [中文pdf, pdf, html, 其他]

标题： 改进的Tanner码解码 显示英文标题

标题： Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

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

[47] arXiv:2501.12834 (交叉列表自 cs.IT) [中文pdf, pdf, html, 其他]

标题： 随机树代码在有限计算资源下的优化 显示英文标题

标题： The Optimization of Random Tree Codes for Limited Computational Resources

B.Tan Bacinoglu

主题： 信息论 (cs.IT) ; 计算复杂性 (cs.CC)

[48] arXiv:2501.13038 (交叉列表自 math.OC) [中文pdf, pdf, html, 其他]

标题： 在性能保证下图灵机上多维函数的迭代优化 显示英文标题

标题： Iterative Optimization of Multidimensional Functions on Turing Machines under Performance Guarantees

Holger Boche, Volker Pohl, H. Vincent Poor

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC)

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

标题： 非统一噪声下通过Pauli反向传播高效模拟参数化量子电路 显示英文标题

标题： Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation

Victor Martinez, Armando Angrisani, Ekaterina Pankovets, Omar Fawzi, Daniel Stilck França

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

[50] arXiv:2501.13762 (交叉列表自 cs.AI) [中文pdf, pdf, html, 其他]

标题： 关于使用LTL算子回答线性单子Datalog查询的数据复杂性的判定（扩展版） 显示英文标题

标题： On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)

Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev

评论： 论文在ICDT'2025上被接受的扩展版本

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