计算复杂性

最近提交的作者和标题

• 2025年07月11日， 星期五
• 2025年07月10日， 星期四
• 2025年07月09日， 星期三
• 2025年07月08日， 星期二
• 2025年07月04日， 星期五

查看今天的 新的 变化

2025年07月08日， 星期二 (继续， 展示 最后 8 之 5 条目 )

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

标题： 一个布尔切片上的近似最优多项式距离引理 显示英文标题

标题： A Near-Optimal Polynomial Distance Lemma Over Boolean Slices

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

评论： 42页，被接受至ICALP 2025

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

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

标题： 通过边查询学习匹配和半图的复杂度 显示英文标题

标题： Complexity of learning matchings and half graphs via edge queries

Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

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

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

标题： 可重命名性测试到子句集类 显示英文标题

标题： Testing for Renamability to Classes of Clause Sets

Albert Brandl, Christian G. Fermüller, Gernot Salzer

期刊参考： 在《第一阶定理证明国际研讨会论文集（FTP'97）》中，Maria Paola Bonacina和Ulrich Fuhrbach主编。RISC-Linz报告系列第97-50号，第34--39页。奥地利林茨约翰内斯·开普勒大学，1997年。

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

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

标题： PFCS：用于确定性数据关系发现的素因数缓存系统 显示英文标题

标题： PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery

Duy Le

评论： 6页，3图，3算法

主题： 数据库 (cs.DB) ; 计算复杂性 (cs.CC)

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

标题： 关于列车路由的可近似性和最小最大不相交路径问题 显示英文标题

标题： On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch

评论： 已被欧洲算法研讨会（ESA）2025接受

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

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

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

标题： Stiefel优化是NP难的 显示英文标题

标题： Stiefel optimization is NP-hard

Zehua Lai, Lek-Heng Lim, Tianyun Tang

评论： 9页

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