arXiv
cs.IT · math.IT
说明基于有限环 F_p[x]/⟨x^4⟩ 零因子图的图码线性码研究
简介本文研究由有限局部环 R=F_p[x]/⟨x^4⟩(p 为奇素数)的零因子图 Γ(R) 导出的线性码。通过 Z*(R) 的等分划,确定了 Γ(R) 二元关联码的参数,并构造了达到对偶最小距离 4 的诱导二部子图码。在 F_p 上,文章给出了邻接码与拉普拉斯码的参数化表示,借助 MacWilliams 恒等式推导了拉普拉斯码的闭式重量分布,并证明其具有 LCD 性质。此外,文章还确定了该图及其矩阵码的自同构群,并从 Γ(R) 的极值子图构造了两族 F_p 上的 Griesmer 最优线性码。
Apurba Sarkar, Kalyan Hansda, and Makhan Maji
arXiv
physics.data-an · cs.IT · math.IT
说明排序可变性:一种熵泛函的理论与两个应用
简介本文研究排序可变性 ζ_S,它是一种具有明确熵性质的信息度量。作者证明 ζ_S 与数据序列的多样性成正比,因此可用香农熵表示,从而把基于压缩的度量与经典信息论联系起来。与保留数据顺序的普通可变性不同,排序可变性去除了顺序,用于刻画观测值的静态分布。文中在二维铁磁 Q 时钟模型和风电出力数据上进行了验证。
Michel Aguilera, Eugenio E. Vogel, Francisco J. Pe\~na 等
arXiv
cs.IT · math.IT
说明HintKD:面向带宽受限云边推理的提示知识蒸馏方法
简介论文针对6G网络中云端与终端协同推理时,传输高维特征或软概率向量占用大量带宽的问题,提出HintKD框架。该方法将教师模型的指导压缩为紧凑的离散提示索引,云端经向量量化映射到码本,终端通过轻量FiLM适配器调制学生特征。实验表明,在DeepSense 6G波束预测任务上,HintKD在保持有竞争力精度的同时,将推理侧通信量降至O(1);在MNIST上的实验也验证了其通用性。
Wanling Luo, Jiayi Zhang, Bokai Xu 等
arXiv
cs.IT · math.IT
说明面向可移动天线辅助无蜂窝大规模MIMO系统的多智能体强化学习
简介本文针对可移动天线带来的非凸最小间距约束,难以联合优化天线位置与传输策略的问题,提出了GLIIR-HAPPO异构多智能体强化学习算法。该方法把原耦合优化分解为协同子问题,将几何约束嵌入带惩罚项的奖励结构,并设计了图结构评论家与角色条件联邦蒸馏机制。仿真结果显示,该框架的和速率明显优于现有多智能体方法,且性能接近集中式方案,同时通信开销大幅降低。
Bokai Xu, Jiayi Zhang, Shuaifei Chen 等
arXiv
cs.AR · cs.DC
说明Lachesis:面向智能体推理、基于生命周期感知的 KV 缓存放置方案(HBM 与高带宽闪存之间)
简介大语言模型推理中,智能体及其子智能体会把上下文累积为 KV 缓存,占用大量内存。高带宽闪存(HBF)容量更大,但写入寿命有限。论文提出 Lachesis,依据数据生命周期将 KV 缓存放置于 HBM 或 HBF,并在不再被读取后释放。模拟结果显示,相较于 HBM 优先的放置方式,HBF 寿命延长 1.19 至 3.13 倍,达到 3.3 至 12.2 个设备年。
Jaehoon Yang, Jeongmin Lee, Haneul Park 等
arXiv
cs.DC · cs.AR
说明vTen:面向领域专用加速器的张量中心验证框架
简介论文指出,张量层面的软件模型与信号级硬件测试平台之间存在语义鸿沟,使领域专用加速器(DSA)的验证效率低下。作者提出 vTen,一个以数据为中心的框架,将验证意图与执行机制严格解耦,并借助声明式 DSL 和按内核粒度的批处理减少主机与仿真器之间的交互次数。在一个生产规模的 3D U-Net 加速器上,相比 Cocotb,vTen 的仿真延迟提升约 2 倍,代码复杂度降低 60.3%。
Chanmin Baek, Keehyuk Lee, Mincheol Cha 等
arXiv
cs.NI · cs.DC · eess.SP
说明6G NeXt:面向6G分体计算网络应用的用例与架构
简介本文介绍研究项目6G NeXt所考虑的两类6G应用场景:全息通信与无人机防碰撞系统,并说明它们对通信与计算基础设施的不同要求。这些场景中的客户端分布广泛且需相互协作,全息通信还需要较高的处理能力,因此需要支持分体计算概念的高速分布式骨干计算基础设施,并与无线网络紧密集成。文章在此基础上给出实现方案,并讨论基于整体通信与计算架构的新技术方法。
Sergiy Melnyk, Qiuheng Zhou, Hans D. Schotten 等
arXiv
cs.IT · math.IT
说明MDS可转换码在分裂区间 r^F<k^F<r^I 下的最优转换带宽
简介本文研究分布式存储中的MDS可转换码,即可将初始码转换为最终码且两者均为MDS码的编码方案。作者针对参数范围 r^F<k^F<r^I 给出了新的秩不等式,并推导出分为三种情形的改进带宽下界。随后,作者为每种情形构造了显式方案,证明该下界是紧的。
Lewen Wang, Sihuang Hu
arXiv
cs.IT · math.IT
说明离散去噪器下近似消息传递的状态演化研究
简介本文研究在硬切片器、量化器、硬阈值等不连续去噪器下的近似消息传递(AMP)算法,指出标准 Onsager 系数会漏掉跳跃点处的边界项。作者针对独立同分布高斯矩阵,证明只要 Onsager 系数包含该边界项,AMP 即遵循状态演化(SE)。4 级和 8 级脉冲幅度调制的仿真显示,修正后的 AMP 能遵循 SE,并接近贝叶斯最优 AMP。
Kuranage Roche Rayan Ranasinghe, Takumi Takahashi, Giuseppe Thadeu Freitas de Abreu
arXiv
cs.DC · cs.PF · cs.SE
说明基于 Python cuda.compute 的 Awkward Arrays GPU 加速
简介Awkward Array 是高能物理领域常用的 Python 库,用于处理嵌套、长度可变的数据。本文基于 Python CUDA Core Compute Libraries(CCCL)为其构建新的 CUDA 执行模型,无需自定义 CUDA 内核,并通过融合多个操作以减少内核启动开销,同时引入惰性执行以优化表达式图。作者报告了相对于此前即时执行方式的性能提升,并强调该设计便于扩展、可与用户自定义 Python 代码结合。
Maksym Naumchyk, Ianna Osborne
arXiv
cs.IT · math.IT
说明非线性函数计算广播的图论界限
简介本文研究非线性函数计算广播问题:发送端持有N份数据,向K个各自带有边信息的用户广播一条公共消息,用户需要获取各自所求的函数。作者借助Körner特征图框架构造广播图,给出适用于任意K、一般信源分布和有限域需求的可达方案,并推导多种下界。结果表明,在部分例子中非线性编码的速率严格优于标量和向量线性方案。
Derya Malak, Vijith Kumar K. P., M. Reza Deylam Salehi
★★★★☆ 值得关注
arXiv
cs.GT
说明资格约束下的在线公平分配
简介该论文研究在资格约束下不可分物品的公平分配,即每件物品只能分给部分符合条件的参与者,这与调度中的受限分配问题等价。作者提出考虑资格的比例公平与无嫉妒公平定义,并在同质估值下分析在线算法的近似界。论文指出,对于物品(goods)与负担(chores)在比例公平上存在明显区别,并给出确定性在线算法的紧致近似因子。
看点提出适用于受限分配的资格感知公平概念,并给出在线近似的紧界(如Θ(√m)与Θ(log m)),理论贡献明确;影响主要限于调度与公平划分的理论子领域。
Joes Biburger, Nicole Megow, Golnoosh Shahkarami
arXiv
cs.IT · math.IT
说明稳定变量的信息瓶颈问题
简介本文将高斯信息瓶颈问题推广到联合稳定分布的变量X和Y,其中X=Y+A,A与Y独立。作者在该设定下求出形式为T=kX+N的最优线性稳定编码器,给出闭式解及临界值。结果显示,除高斯情形外,此类随机线性编码器并非最优,但在压缩率很大时渐近最优;线性解在联合高斯情形下可还原为经典高斯信息瓶颈。
Dongmin Park, Jihad Fahs, Mohamad Assaad
arXiv
cs.IT · math.IT
说明面向局部差分隐私离散信道的稀疏核机制
简介本文研究由非负核和依赖输入的可容许输出支撑集生成的稀疏离散局部隐私机制。文中给出了该稀疏核类的纯与近似局部差分隐私的精确刻画,并将近似情形下的隐私损失分解为支撑泄漏与重叠超额损失两项。文中还把结果应用于稀疏阶梯机制、稀疏随机响应、Skellam 扰动等具体离散机制族。
Amirreza Zamani, Parastoo Sadeghi, Mikael Skoglund
arXiv
cs.DC · cs.NI
说明用于可验证数字馆藏对象的私有 IPFS 数据保存库
简介该论文在柏林自然博物馆部署了一个由七个节点组成的私有 IPFS(星际文件系统)原型,用于存放原始采集数据。原型通过内容标识符(CID)成功恢复了两个真实采集文件夹,并纳入了一个大型机器学习模型权重文件夹,同时对节点运行状态进行了持续监测。研究认为,该架构可为馆藏数字对象提供可验证、可恢复的内部分布式存储方案。
Joachim Snellings, Jasper Funk-Smit, Margot Belot 等
arXiv
cs.GT · econ.TH
说明在权益证明治理中奖励知情投票
简介本文研究委托代表的奖励设计:代表需要付出成本获取信息,并就一项二元治理提案投票。研究表明,在非中性先验下,没有任何支付规则能让真实投票在所有正努力水平下严格最优;在大型对称委员会中,固定预算也会限制决策准确度。文章比较了按比例分配与仅奖励足够大获胜联盟成员的条件规则,后者能使对称正努力下的真实投票严格最优,并在适当条件下带来更高努力和决策准确度。不过,不真实的均衡仍可能同时存在。
Juan Beccuti, Manvir Schneider
arXiv
cs.IT · math.IT
说明城市环境中利用低轨卫星机会信号的导航:GLRT辅助的离网稀疏贝叶斯学习方法
简介本文针对城市中全球导航卫星信号易受遮挡和干扰的问题,研究利用低轨卫星机会信号进行定位导航。作者提出结合广义似然比检验与离网稀疏贝叶斯学习的框架,用于多径和非高斯、有色噪声环境下的视线时延-多普勒参数估计,并通过扩展卡尔曼滤波器得到导航解。仿真结果显示,在城市环境中该方法相比基于GLRT的估计,时延均方根误差最多降低77%,位置均方根误差降低88.5%。
Maedeh Sotoodenia, Mohammad Hossein Kahaei, Alireza Nezamalhosseini
arXiv
cs.GT · cs.CC
说明相关先验下一价拍卖中混合均衡的计算复杂度
简介本文证明,在离散一价拍卖且竞拍者先验相关的情形下,计算近似的混合贝叶斯-纳什均衡属于 PPAD 完全问题。论证的关键中间步骤,是证明在一种新的标准型博弈(超图离散一价拍卖)中计算近似纳什均衡同样是 PPAD 完全的,该结果本身也可能具有独立价值。
Mark Chen, Xi Chen, Hao Cui 等
★★★★☆ 值得关注
arXiv
cs.DC
说明FailBench:跨分布式训练架构评估容错机制
简介该论文提出FailBench统一评测框架,涵盖7种分布式训练架构、8种崩溃容错机制及无容错基线,并测试单点、并发和级联的停机故障。作者在8张V100集群上评估了142组组合,结果显示没有机制普适最优,且机制开销强烈依赖于架构;其中内存复制开销在3.7%至176%之间。作者还据此给出了选择容错机制的决策框架,并开源了该框架。
看点通过统一框架系统比较七种并行架构与八种容错机制,并提出选型决策框架;实验覆盖142组组合,证据较扎实,影响面主要在分布式训练领域。
Khaled Aljbab, Amine Barrak
arXiv
cs.IT · math.IT
说明用于高灵敏度无线通信的冷原子里德堡阵列与时空复用方案
简介本文研究了一种冷原子里德堡阵列(CoRA)架构,用于克服经典电磁接收机的热噪声限制,以及热蒸气原子接收机中的多普勒展宽和光子散粒噪声。文中提出基于子阵列调度的时空复用(STM)框架,实现符号询问无间隙,并提出基于联合二项粒子平滑器(JBPS)的信号检测方法。数值结果显示,所提方案解决了连续采样的时间瓶颈,JBPS可降低误码率,并揭示了灵敏度与可持续重复率之间的权衡。
Jian Xiao, Tierui Gong, and Chau Yuen
arXiv
cs.IT · math.IT
说明面向连续透射型RIS多用户通信的联合波束成形
简介本文研究连续透射型可重构智能表面(CT-RIS)辅助的多用户下行通信,其无源波束成形由定义在连续孔径上的相位函数刻画。基站到CT-RIS链路采用随距离变化的球面波模型,CT-RIS到用户链路采用基于场响应向量的有限路径模型。作者构建加权和速率最大化问题,联合优化有限维的基站预编码和无限维的相位函数,并提出交替优化算法求解。数值结果显示,该方案性能优于所比较的基准方案。
Beining Han, Shumeng Zhang, Deyou Zhang 等
arXiv
cs.DC · cs.AR
说明TRANSIT:面向多节点大模型训练的透明缩容框架
简介TRANSIT 是一个透明的缩容框架,让多节点模型训练能用更少的 GPU 完成,并把 CPU 内存作为 GPU 显存的扩展。它通过用户空间拦截层实现,无需修改应用、训练框架、调度器、驱动或操作系统。论文在多达 64 块 H100 GPU 上评测稠密模型与 MoE 模型,报告相比 TorchTitan、ZeRO-Offload 和 ZeRO-Infinity 的单 GPU 吞吐量最高分别高出 68%、59% 和 42%,并可用少 50% 的 GPU 维持超过 90% 的基线吞吐量。
Hyungyo Kim, Nicholas Satchanov, Hrishi Shah 等
arXiv
cs.DC
说明NCCL M2N:面向分布式张量重分片的布局与拓扑感知集合通信原语
简介论文提出 NCCL M2N,一种用于分布式张量重分片的集合通信原语,可根据源端与目标端的网格和放置方式推导传输区域与全局通信调度。在 256 块 GB200 GPU 上,单个 FFN-MoE 层传输相比朴素直接发送最高加速 7.9 倍;在 DeepSeek-V3 的 NeMo-RL 实验中,权重同步时间从 5.78 秒降至 2.77 秒,步骤时间减少 12.7%。
Kaushik Kandadi, Youngeun Kwon, Sreeram Potluri 等
arXiv
cs.DC
说明Mosaic:通过内核级干扰预测实现有延迟保障的GPU共享
简介本文提出Mosaic,一种内核级GPU干扰预测器,结合解析模型与轻量学习模型,显式建模线程块放置、内存层级争用和SM内资源争用等干扰机制。在四种GPU架构上,其预测误差相比已有预测器最多降低一个数量级。作者将其集成到调度器MosaicSched中,在满足延迟服务等级目标的前提下,通过在整GPU共享与SM分区之间选择来提高尽力而为任务的吞吐量。
Foteini Strati, Ethan Graham, Leo Stephan 等
arXiv
cs.DC
说明高性能计算中的生产力:从代码行数与性能可移植性到AI辅助编程的批判性综述
简介本文对高性能计算(HPC)中的生产力度量进行批判性综述,梳理了从源代码行数(SLOC)、静态复杂度、实证可用性研究到开发时间模型与语义方法的发展脉络。文章还讨论了自动迁移与AI辅助编程如何削弱代码变换与人力投入之间的对应关系,使工作重心转向验证、修正和性能调优。最后比较了各类方法的测量对象、直接性、客观性和可复现性,并指出定量评估HPC生产力仍面临的主要局限与挑战。
Ami Marowka
arXiv
cs.NI · cs.DC
说明开放云测试平台中面向科学计算的高速网络处理
简介本文提出一种基于FPGA的SmartNIC架构,用于应对数据密集型科学计算中的网络挑战。系统以P4可编程数据面实现报文解析、标记、遥测提取、流量导向和机器学习推理,无需主机CPU参与。实验在开放云测试平台的AMD U280 FPGA上进行,结果显示该方法可实现线速报文处理,处理延迟极小,并能准确监测科学数据流。
Miriam Leeser, Michael Zink, Suranga Handagala 等
★★★★☆ 值得关注
arXiv
cs.IT · math.IT
说明覆盖深度问题的最优码与随机码性能
简介DNA 存储通过随机抽取合成的 DNA 链读取信息,因此恢复所需的读取次数是关键性能指标。本文研究覆盖深度问题,即寻找使随机抽样列张成整个信息空间所需期望次数最小的线性码。作者给出了该期望的通用公式,并证明 q 元单纯形码和 q 元汉明码在相应参数下是最优的。此外,文章分析了随机线性码的期望覆盖深度,指出在固定码率情形下,其与 MDS 基准的加性差距不随码长增加而增长。
看点推导了覆盖深度期望的通用公式,并证明单纯形码与汉明码的最优性,理论上有实质推进,影响限于编码理论子领域。
Roee Gross, Yitzchak Grunbaum, Matteo Bertuzzo 等
arXiv
cs.DC · cs.DS
说明拜占庭容错的因果单播:消息空间开销为常数
简介本文提出一种拜占庭容错的因果有序算法,用于点对点消息,其应用消息空间开销为常数 O(1)。算法采用发送者许可发送不变式和隔离缓冲乐观模型,并为每个对等方设置独立队列,以抵御状态钉死和队头阻塞攻击。作者证明该算法保证系统级活性,并满足一种弱化的因果安全抽象,称为拥塞松弛因果交付。
Purv Patel, Ajay D. Kshemkalyani
arXiv
cs.GT · cs.SY · eess.SY
说明基于度量的非合作可微博弈均衡选择:通过条件化学习动态的度量来决定学习最终收敛到哪个均衡
简介该论文研究如何用随状态变化的对称正定度量改变学习动态的收敛方向,而不改变博弈的均衡点。作者刻画了何时能让一个竞争均衡变得不稳定,并在连续承诺的猎鹿博弈和熵正则化的重复囚徒困境中验证了方法,两者都能选出目标均衡。
Karan Mahesh, Runyu Zhang, Michael R. Benjamin 等
arXiv
cs.DS · cs.GT · math.OC
说明用STARS进行存储交易:算法设计与基本极限谱系
简介本文研究在线交易问题:交易者依次面对来自已知分布、取值于[0,1]的独立同分布价格,并受存储约束做出不可撤销的买入、卖出或持有决策。作者以遗憾(事后最优策略与在线算法期望利润之差)衡量算法表现,并引入参数β刻画价格在中位数附近的集中程度。提出了名为STARS的算法,通过模拟多种未来价格情景来近似未来价值函数,文中证明其在多类分布上接近最优的表现。
Jerry Anunrojwong, Akshit Kumar, Rachitesh Kumar
arXiv
cs.IT · math.IT
说明用信息论方法重建未破译信息的几何与结构特征
简介本文将作者此前关于从非随机信息中恢复几何与拓扑的框架,扩展到费斯托斯圆盘、安第斯结绳、拉帕努伊木板、印度河文字和沃伊尼奇手稿等未破译文献,并以埃及图表和阿雷西博信息作为对照。研究以算法信息动力学为指导,结合信息度量、压缩与算法概率估计,识别结构上的可恢复组织,但并不解读其语义。
Hector Zenil, Abicumaran Uthamacumaran
★★★★★ 值得关注
arXiv
cs.NI · cs.DC · cs.PF
说明Ofan:面向 AI 训练的最优负载均衡方案
简介本文针对 AI 训练流量在满线速发送时,现有逐包喷洒(packet spraying)负载均衡算法效率不足的问题展开研究。作者指出,在胖树(fat tree)拓扑中,报文一旦选定上行路径,通往目的地的下行路径便唯一确定,与目的地无关的方案无法消除由此产生的不均衡。论文提出交换机端的目的地感知负载均衡方案 Ofan 及其适配现有交换机流水线架构的变体 pOfan,并给出 P4 实现与基于 Llama-3 405B 模型的 FSDP2 端到端评估结果。
看点提出目的地感知的负载均衡方案,证明了已有方案的$\Theta(\sqrt{m})$排队问题并给出$O(1)$界,结合P4实现与大模型训练端到端评测,证据较充分。
Sarah McClure, Evyatar Cohen, Jakob Krebs 等
★★★★☆ 值得关注
arXiv
math.NT · cs.DC · cs.MS
说明CUDA-MPQS:全程驻留GPU的自初始化二次筛法,并分解了RSA-155
简介本文提出CUDA-MPQS,一种自初始化的二次筛法(QS),其各阶段(多项式初始化、筛选、关系后处理、大素数匹配、GF(2)矩阵构建、Block Wiedemann线性代数及平方根计算)均在GPU上执行。作者借此端到端分解了512位RSA-155挑战模数,总计耗时700.6 GPU小时、约242千瓦时,其中98.4%用于筛选。文中称这是二次筛法分解过的最大整数,超过此前的RSA-150纪录。
看点将二次筛法所有阶段完整迁移到GPU并分解RSA-155,新颖性较强;实验对比充分,但缺乏公开代码的说明,影响面限于特定算法。
Fabian Januszewski, Christoph Heinrichs
★★★★★ 值得关注
arXiv
cs.GT
说明重审确定占优策略机制设计的困难性
简介本文研究组合拍卖中确定占优策略激励相容(DSIC)机制的通信复杂度,考察不同估值类别下可达到的近似比。作者证明了一般单调、XOS 与总替代(GS)估值下的下界,其中 GS 下界回答了此前的一个公开问题。文中还给出两个竞标者情形下的若干结果,包括一个多项式通信的 (1+√5)/2 近似机制。
看点给出确定性DSIC机制通信复杂度的统一下界并回答GS开放问题,两方情形也有新的近似结果,证明严格,影响理论社区。
Frederick V. Qiu
arXiv
math.CO · cs.GT · cs.IT
说明对称格拉斯曼公式:单调维数缺陷层级
简介本文研究任意域上有限个子空间之和的维数缺陷,推导出一个对称、非递归的格拉斯曼型维数公式,用于计算它们之和的维数。该公式通过一个指定子空间与其余子空间部分和的交来表示总维数损失,并证明缺陷层级单调,给出可表示拟阵的 Shapley 值解释。
Masoud Gharahi, Diego Ponterio
arXiv
cs.DC
说明跨多块 GPU 的全局束搜索:面向十亿级记录规模的高吞吐束搜索
简介本文研究如何让多块 GPU 作为一次搜索协同完成束搜索,即使保留的候选集无法放进单块设备。状态和候选始终留在 GPU 上,CPU 只接收少量控制与祖先记录。作者证明,在满足完整候选、整数分数、Hash128 等价及物理布局并列顺序等条件,且每个键只做一次全局归约、路由无竞争时,分布式流水线返回与单机相同的 top-B 结果。在八块 H200 上,一次 Cube4 运行在 931.266 秒内完成深度 8 的饱和搜索,有效宽度为 2,900,361,216,推导出约每秒 7474.6 万个父–生成器对。
Ivan Litvak
arXiv
cs.DC
说明OrigaMIG:面向 MIG 的虚拟机放置优化与在线迁移
简介本文针对 NVIDIA 多实例 GPU(MIG)在云数据中心中因放置规则导致的碎片化问题,将 MIG 感知的虚拟机放置建模为二进制整数线性规划(BILP),目标是提高请求接纳率、整合资源并减少迁移开销。作者提出 OrigaMIG:新请求先用轻量贪心规则放置,仅在无法放置或 GPU 出现碎片时,才在小范围物理机邻域上求解 BILP 并以实时迁移执行。仿真结果显示,在 128 台物理机(256 块 A100 和 A30 GPU)上,相比较强的基线策略,OrigaMIG 保持的活跃物理机更少且迁移的虚拟机减少 29% 至 49%。
Ahmad Siavashi, Mahmoud Momtazpour
arXiv
cs.ET · cs.DC · cs.PL
说明加速量子计算普及的经典-量子混合解决方案
简介本文讨论经典-量子混合计算的软件层面,考察云应用、中间件框架和API网关等可让经典计算与量子计算协同工作的现有方案。文中为从业者整理了算法、全栈库、模拟器和云服务提供商的清单,并提出混合软件工程的未来研究议程与近期开发重点。作者认为,由于量子执行深度依赖经典的前后处理,混合计算可能是长期存在的形态,而非过渡性的权宜之计。
Advait Deshpande, Luciano Baresi, Arosha K. Bandara
★★★★☆ 值得关注
arXiv
cs.GT
说明论效率的脆弱性:一名偏离者下的无耦合学习
简介论文研究博弈中的无耦合学习:玩家仅依据自身过去的行动与效用,能否在不沟通的情况下达到总效用最大化的高效结果。作者以一种已有的福利最大化学习算法为测试对象,考察只有一名玩家偏离该算法时的长期行为。结果显示,单个偏离者即可显著改变算法的长期走向,且任何无耦合算法都无法在所有博弈中抵抗这类偏离者。
看点提出单个偏离者即可破坏完全无耦合福利最大化学习的鲁棒性,并证明无算法在所有博弈中都能抵御,理论结论有新意且论证较完整。
Vade Shah, Jason R. Marden
★★★★☆ 值得关注
arXiv
cs.GT
说明通过递归困难实例改进双边贸易中随机出价者机制的上界
简介本文研究双边贸易中随机出价者机制相对于最优贸易收益的最坏情况效率。作者构造了一族独立的买方估值与卖方成本分布,其比值趋近于0.436943488……,优于此前的上界0.460242308……。该构造结合了递归嵌套的卖方分布与买方估值的向下运输,并通过递推关系给出极限常数的解析刻画。
看点通过递归嵌套的卖方分布构造新的困难实例,把随机出价机制效率上界从0.4602改进到0.4369,并给出解析刻画。
Heyang Shang, Jing Chen
★★★★☆ 值得关注
arXiv
cs.IT · math.IT
说明基于匹配长度相关窗口的Lempel-Ziv分段:普适性与极限
简介LZ77编码器对每个匹配的距离都分配相同位数,但长距离的短匹配往往得不偿失。该文研究按匹配长度决定可回溯范围的窗口方案:长度为ℓ的匹配最多只能回指W(ℓ)个符号,短匹配的距离字段更短。文章分析了这种方案带来的损失,并证明在一定条件下贪心分段仍保持LZ77的收敛速率与普适性,同时讨论了冗余项及相关编码改进的收益。
看点证明了长度相关窗口LZ77在贪心解析下的通用性与收敛速率,并给出冗余项的紧下界,理论贡献突出,但影响主要限于信息论子领域。
Yingquan (Cody) Wu