计算复杂性

最近提交的作者和标题

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

查看今天的 新的 变化

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)