计算复杂性

2025年01月 的作者和标题

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

标题： 是否量子计算使用非局域资源在操作上是不可判定的 显示英文标题

标题： Whether a quantum computation employs nonlocal resources is operationally undecidable

Chris Fields, James F. Glazebrook, Antonino Marciano, Emanuele Zappala

评论： 15页

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

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

标题： 基于图着色的量子电路优化 显示英文标题

标题： Quantum Circuit Optimization by Graph Coloring

Hochang Lee, Kyung Chul Jeong, Panjin Kim

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

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

标题： 第二价格拍卖中定价均衡的常数不可近似性 显示英文标题

标题： Constant Inapproximability of Pacing Equilibria in Second-Price Auctions

Xi Chen, Yuhao Li

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

[54] arXiv:2501.15312 (交叉列表自 math.PR) [中文pdf, pdf, html, 其他]

标题： 图灵在诺贝尔和阿贝尔奖的阴影中：两项最近奖项背后的算法故事 显示英文标题

标题： Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

David Gamarnik

评论： 将出现在《美国数学学会通报》上

期刊参考： 美国数学学会通报，2025年5月

主题： 概率 (math.PR) ; 统计力学 (cond-mat.stat-mech) ; 计算复杂性 (cs.CC) ; 优化与控制 (math.OC)

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

标题： Fitting-自由群的最小忠实排列次数的复杂性 显示英文标题

标题： Complexity of Minimal Faithful Permutation Degree for Fitting-free Groups

Michael Levet, Pranjal Srivastava, Dhara Thakkar

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

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

标题： 对称感知机，数的划分和格子 显示英文标题

标题： Symmetric Perceptrons, Number Partitioning and Lattices

Neekon Vafa, Vinod Vaikuntanathan

主题： 统计理论 (math.ST) ; 计算复杂性 (cs.CC) ; 数学物理 (math-ph) ; 概率 (math.PR)

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

标题： 网格上LCL问题的复杂性类分离 显示英文标题

标题： Separating complexity classes of LCL problems on grids

Katalin Berlow, Anton Bernshteyn, Clark Lyons, Felix Weilacher

评论： 36页，5幅图

主题： 逻辑 (math.LO) ; 计算复杂性 (cs.CC) ; 组合数学 (math.CO) ; 概率 (math.PR)

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

标题： 实验性相对论零知识证明与无条件安全性 显示英文标题

标题： Experimental relativistic zero-knowledge proofs with unconditional security

Chen-Xun Weng, Ming-Yang Li, Nai-Rui Xu, Yanglin Hu, Ian George, Jiawei Wu, Shengjun Wu, Hua-Lei Yin, Zeng-Bing Chen

评论： 24页，8图

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

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

标题： 去中心化的投影自由在线上界线性可优化化及其在DR-次模优化中的应用 显示英文标题

标题： Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC) ; 机器学习 (cs.LG) ; 机器学习 (stat.ML)

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

标题： 晚点总比不点好？ 在时间图中选择延迟以满足乘客需求的难度 显示英文标题

标题： Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs

David C. Kutner, Anouk Sommer

评论： 20页，7图

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

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

标题： 一种单循环SPIDER型期望约束非凸非光滑优化随机次梯度方法 显示英文标题

标题： A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

Wei Liu, Yangyang Xu

评论： 关键词：随机，次梯度，期望约束，弱凸，公平性约束分类

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC) ; 机器学习 (cs.LG) ; 数值分析 (math.NA)