计算复杂性

最近提交的作者和标题

• 2025年07月21日， 星期一
• 2025年07月18日， 星期五
• 2025年07月17日， 星期四
• 2025年07月16日， 星期三
• 2025年07月15日， 星期二

查看今天的 新的 变化

2025年07月21日， 星期一 (继续， 展示 最后 6 之 1 条目 )

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

标题： 斯特拉森$2\times2$矩阵乘法从三维体积形式 显示英文标题

标题： Strassen $2\times2$ Matrix Multiplication from a 3-dimensional Volume Form

Benoit Jacob (AMD)

评论： 13页

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

2025年07月18日， 星期五 (展示 5 之 5 条目 )

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

标题： 从NP难性得出的计算统计权衡 显示英文标题

标题： Computational-Statistical Tradeoffs from NP-hardness

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan

评论： 出现在FOCS 2025上

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

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

标题： 完美扩散是$\mathsf{TC}^0$ -- 无效扩散是图灵完备 显示英文标题

标题： Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete

Yuxi Liu

评论： 7页

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

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

标题： 公式一：超越竞赛编程的算法推理深度测量 显示英文标题

标题： FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming

Gal Beniamini, Yuval Dor, Alon Vinnikov, Shir Granot Peled, Or Weinstein, Or Sharir, Noam Wies, Tomer Nussbaum, Ido Ben Shaul, Tomer Zekharya, Yoav Levine, Shai Shalev-Shwartz, Amnon Shashua

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

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

标题： 排序向量聚类：理论与应用 显示英文标题

标题： Ranking Vectors Clustering: Theory and Applications

Ali Fattahi, Ali Eshragh, Babak Aslani, Meysam Rabiee

主题： 机器学习 (cs.LG) ; 计算复杂性 (cs.CC) ; 应用 (stat.AP) ; 方法论 (stat.ME)

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

标题： 串行缩放假说 显示英文标题

标题： The Serial Scaling Hypothesis

Yuxi Liu, Konpat Preechakul, Kananart Kuwaranancharoen, Yutong Bai

评论： 28页（13页正文+附录与参考文献），8张图，共同第一作者

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

2025年07月17日， 星期四 (展示 2 之 2 条目 )

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

标题： 哪些图基序参数被计数？ 显示英文标题

标题： Which graph motif parameters count?

Markus Bläser, Radu Curticapean, Julian Dörfler, Christian Ikenmeyer

评论： 40页，完整版

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

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

标题： 在随机（log n）-CNF中查找被否定的子句对于随机通信来说是困难的 显示英文标题

标题： Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

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

2025年07月16日， 星期三 (展示 6 之 6 条目 )

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

标题： 关于低阶Skolem问题的复杂性 显示英文标题

标题： On the Complexity of the Skolem Problem at Low Orders

Piotr Bacik, Joël Ouaknine, James Worrell

评论： 19页

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

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

标题： 等式比常数成本通信弱得多 显示英文标题

标题： Equality is Far Weaker than Constant-Cost Communication

Mika Göös, Nathaniel Harms, Artur Riazanov

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

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

标题： 对称马尔可夫链在多重切片上的特征值边界及其应用 显示英文标题

标题： Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

评论： 将出现在 RANDOM 2025 中

主题： 计算复杂性 (cs.CC) ; 概率 (math.PR)

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

标题： 关于扩展形式博弈中最优相关均衡的复杂性 显示英文标题

标题： On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games

Vincent Cheval, Florian Horn, Soumyajit Paul, Mahsa Shirmohammadi

主题： 计算机科学与博弈论 (cs.GT) ; 计算复杂性 (cs.CC)

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

标题： FPT 分参数化分数和广义超树宽度 显示英文标题

标题： FPT Parameterisations of Fractional and Generalised Hypertree Width

Matthias Lanzinger, Igor Razgon, Daniel Unterberger

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

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

标题： 一个平均情况下的超图着色预言机 显示英文标题

标题： A Fast Coloring Oracle for Average Case Hypergraphs

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber

评论： 18页，2图

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

2025年07月15日， 星期二 (展示 10 之 10 条目 )

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

标题： 通信复杂性是NP难的 显示英文标题

标题： Communication Complexity is NP-hard

Shuichi Hirahara, Rahul Ilango, Bruno Loff

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

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

标题： 有向不相交路径问题在没有大网格子图的无环有向图上仍然是W[1]-难的 显示英文标题

标题： Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors

Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani, Jacob Stegemann

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

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

标题： IPS下界对于公式和ROABP之和 显示英文标题

标题： IPS Lower Bounds for Formulas and Sum of ROABPs

Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu

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

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

标题： 对邓的“P=NP”的批评 显示英文标题

标题： A Critique of Deng's "P=NP"

Isabel Humphreys, Matthew Iceland, Harry Liuson, Dylan McKellips, Leo Sciortino

评论： 10页，4图

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

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

标题： 指针追踪的通信复杂性通过固定集引理 显示英文标题

标题： Communication complexity of pointer chasing via the fixed-set lemma

Emanuele Viola

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

[25] arXiv:2507.10413 (交叉列表自 cs.DC) [中文pdf, pdf, html, 其他]

标题： 一致性，不一致，涌现：次协调性与之有什么关系？ 显示英文标题

标题： Consensus, Inconsistency, Emergence: what's paraconsistency got to do with it?

Gabriel Rocha

评论： 10页

主题： 分布式、并行与集群计算 (cs.DC) ; 计算复杂性 (cs.CC) ; 信息论 (cs.IT) ; 计算机科学中的逻辑 (cs.LO)

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

标题： 带有受限链路使用的同步网络设计 显示英文标题

标题： Simultaneous Network Design with Restricted Link Usage

Naonori Kakimura, Péter Madarasi, Jannik Matuschke, Kitti Varga

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 优化与控制 (math.OC)

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

标题： 关系代数的网络满足问题，最多有4个原子 显示英文标题

标题： The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

Manuel Bodirsky, Moritz Jahn, Matěj Konečný, Simon Knäuer, Paul Winkler

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

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

标题： m-永恒支配和某些有限和无限图类上的变体 显示英文标题

标题： m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs

Tiziana Calamoneri, Federico Corò, Neeldhara Misra, Saraswati G. Nanoti, Giacomo Paesani

评论： 被接受在FCT 2025上进行展示

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

[29] arXiv:2507.08844 (交叉列表自 cs.CR) [中文pdf, pdf, html, 其他]

标题： 不可变性不保证信任：形式与逻辑的反驳 显示英文标题

标题： Immutability Does Not Guarantee Trust: A Formal and Logical Refutation

Craig S Wright

评论： 8页

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