其它计算机科学 · 2026年10月23日(周五)

分布式计算、博弈论、信息论等。

★★★★☆ 值得关注
arXiv math.CO · cs.IT · math.IT

A probabilistic construction of maximum h-scattered subspaces

说明概率构造最大 h-分散子空间(有限域上线性向量空间的一类组合结构)

简介本文研究有限域上的线性子空间,即最大 h-分散子空间,它与 MRD 码等编码理论概念相关。作者用随机矩阵在特定代数上构造子空间,并证明当维数 r 满足给定不等式且 (h+1) 整除 rn 时,这类子空间存在。文中还由此推出 F_{q^n}-线性 MRD 码在码长足够大时的存在性。

看点用概率方法构造最大h-scattered子空间,显著改进了存在性界限,并给出MRD码存在性结论,理论证明完整严谨,影响限于编码理论子领域。

Alessandro Giannoni, Alessandro Neri

arXiv cs.DC · cs.NI

Migration as a Steady-State Execution Primitive: A Runtime for Virtual Stationarity in Low-Earth Orbit

说明将迁移作为稳态执行原语:低轨道中虚拟静止的运行时

简介该论文针对低轨卫星星座中因卫星高速运动而需要持续切换宿主的问题,提出“虚拟静止”概念,即应用需不断迁移到经过的卫星上以保持逻辑上的地理邻近。作者把实时迁移重新表述为稳态执行模型,并设计了虚拟静止运行时(VSR)框架。实验显示,在物理异构主机上,300次周期性切换的95百分位停机时间低于6毫秒,1600颗卫星的仿真也确认迁移可在轨道切换窗口内完成。

Daniel Kleebinder, Alireza Furutanpey, Stefan Nastic

arXiv cs.DC

Beyond Hotness: High-Resolution Memory Characterization of Cloud and LLM Workloads for Tiered Memory with ARM SPE

说明超越热度:利用 ARM SPE 对云与大模型负载进行高分辨率内存特征分析,以支持分层内存

简介本文提出一种高分辨率内存特征分析方法,用于研究数据分析和大语言模型负载在多层内存中的适用机会。作者基于 ARM 的统计性能剖析扩展(SPE)实现该方法,并对 CloudSuite 与大模型应用中的八个内存密集型负载进行了分析。研究识别了区域性访问模式,评估了面向云的缓存层级的效果,并提出基于内存空闲期和延迟特征的新指标,用于确定分层内存中的数据放置位置。

Jie Ren, Ivy Peng

arXiv cs.DB · cs.DC

Tile-Based Decompression in Compiled GPU Engines

说明编译型GPU引擎中基于分块的解压缩

简介本文针对GPU内存预算紧张的问题,提出一种用于编译型GPU查询引擎的压缩子系统,把解压缩作为一等物理算子处理,并在Proteus中实现。其编译器集成的共享内存方案,在单个生成的GPU内核中将协作式分块解压与逐元组查询执行融合,避免在HBM中物化解压后的列。与HeavyDB和Sirius相比,该方案在GPU常驻数据上查询时间具有竞争力,同时内存占用最多降低4倍,内存带宽消耗最多降低6倍。

Antonio Boffa, Ananya Gupta, Hamish Nicholson 等

arXiv cs.DC · cs.AR · cs.PF

Toward Open ISA Supercomputing: A Comparative Study of RISC-V, Arm, and x86 Architectures on HPC Workloads

说明迈向开放指令集超级计算:RISC-V、Arm 与 x86 架构在 HPC 负载上的对比研究

简介本文在统一的软件环境和测试方法下,比较了 Sophgo SG2044(RISC-V)与 NVIDIA Grace 和 Intel Xeon 8480+ 在 STREAM、HPL、HPL-MxP、HPCG 四项基准及四个应用上的表现。结果显示,SG2044 绝对性能比 Arm 和 x86 系统低 8 至 15 倍,但在若干负载上扩展性和能效具有竞争力;其 64 核的大模型解码结果在所测平台中相对扩展性和能效最高。作者认为 RISC-V 处理器正在缩小与主流架构的差距。

Emanuele Venieri, Giacomo Madella, Gabriele Ceccolini 等

arXiv cs.NI · cs.DC · cs.PL

GLP Networking API Specification

说明GLP 网络接口规范:为 madGLP 提供底层网络层的技术规范

简介本文为 madGLP(多智能体确定性 GLP)规定其底层网络层。各智能体运行在用户手机上,仅通过异步消息传递通信,网络层只提供 GLP 无法自行实现的网络栈、位置服务、应用认证与密码学原语。系统支持蓝牙低功耗、局域网和经穿透的广域网三种传输方式,并通过 Noise 会话与应用证明建立互相认证的通信,消息协议保证公平、无序、原子且经认证的投递。

Dan Bachar, Ehud Shapiro

★★★★☆ 值得关注
arXiv cs.PL · cs.DC

On the Expressiveness of Asynchronous Processes with Nested Session Types

说明异步进程与嵌套会话类型的表达能力研究:证明其图灵完备

简介本文研究的是异步会话进程(ASP)的表达能力,这是与嵌套会话类型(NSTs)相关的进程模型。嵌套会话类型可以描述嵌套递归协议,而传统会话类型只能描述正则协议。作者通过把双计数器机正确编码为带类型进程,证明了该模型是图灵完备的,编码中使用了由 NSTs 约束的、感知状态的计数器与指令表示。

看点证明了带嵌套会话类型的异步进程模型图灵完备,通过将双计数器机编码为类型化进程完成证明,给出了已知表达力界限的显著推进。

Sjors Wortelboer, Dan Frumin, Jorge A. P\'erez

arXiv cs.IT · math.IT

Distortion-Rate Outage Probability for Non-ergodic Classes of Sources

说明非遍历信源类的失真-速率中断概率

简介该论文讨论信源编码中的“中断”概念。在信源统计不具遍历性时,作者定义了中断,讨论相关性质,考察紧致信源类的特例并给出示例。

Dongmin Park, Ibrahim Abou-Faycal, Razane Tajeddine

★★★★★ 值得关注
arXiv cs.DS · cs.GT

Pareto-optimal Scheduling with Predictions

说明带预测的帕累托最优调度

简介本文研究带预测的抢占式单机调度问题,预测内容为作业的顺序或大小,目标是最小化总完成时间。作者精确确定了确定性算法在一致性与鲁棒性之间的最优权衡,给出了对应的贪心算法,并证明该权衡无法被改进。

看点论文精确刻画了确定性算法一致性与鲁棒性的最优权衡,给出匹配的上下界,显著改进此前Θ(1/ε)的结果,理论证明完整。

Ziyad Benomar, Vianney Perchet

arXiv cs.DB · cs.DC

MetaDB: Putting File-System Structure Back into Distributed Databases

说明MetaDB:把文件系统结构带回分布式数据库

简介本文介绍百度的元数据感知分布式事务数据库MetaDB,作为其大规模存储系统的共享元数据层。它针对数据模型、事务模型和存储实现三类与元数据负载不匹配的问题,采用树形拓扑分片、关键路径外的语义处理以及生命周期感知存储引擎等方法。文中称其吞吐量为原系统的2.2至4.1倍,元数据机器数量减半,并已在生产环境运行五年以上,单集群可扩展到1000多个元数据节点。

Zebin Ren, Biao Cao, Kang Chen 等

arXiv math.CO · cs.IT · math.IT

A counterexample to Tokareva's conjecture on sums of two bent functions

说明Tokareva猜想在两个bent函数之和上的反例

简介论文讨论布尔函数能否写成两个bent函数之和:偶数维n≥4时,两个bent函数之和的代数次数不超过n/2,Tokareva猜想其逆命题也成立。作者证明在8维中,x1x2(x3x4+x5x6+x7x8)不能写成两个bent函数之和,从而否定该猜想,并将构造推广到所有偶数维n≥8。此外,借助Shaporenko的归约方法,作者给出了所有偶数维n≥10时Tokareva导数猜想的显式反例。

Yansong Feng, Hao Jiang, Guancheng Li 等

arXiv cs.IT · math.IT

Encoding-Sensitive Nullstellensatz Certificates for Syndrome Exclusion in LDPC Codes: Sharp Local Bounds and a Linear Separation

说明LDPC码综合征排除的编码敏感零点定理证书:精确局部界与线性分离

简介该论文研究如何证明LDPC码校验矩阵中不存在至多t个变量节点、使至多b个校验未被满足的非空集合,这与最小距离和陷阱集分析相关。作者以Nullstellensatz证书表示这种不可行性,并比较两种基数约束编码方式的证书次数:局部编码可构造次数不超过t+b+K+1的证书,其中K与最大校验度呈对数关系且与码长无关;标准计数编码则给出与码长呈线性的下界。所有计算结果均以精确有理数算术验证。

Malihe Aliasgari, Hassan Khodaiemehr, and Khadijeh Bagheri

arXiv cs.DC

Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms

说明通过分层算法限制突发式高性能计算作业的排队等待,实现公平调度

简介高性能计算集群由多个项目共享,突发性提交使少数重度用户挤占资源,偶尔提交的用户要承受不可预知的排队延迟。论文提出HyDRA调度器,为每个作业在到达时分配截止时间,结合优先级评分和公平性约束来限制等待时间。基于ALCF Polaris一年的作业轨迹进行评估,结果显示其项目级Jain公平性指数是最佳基线的2倍,并在利用率上有适度代价。

Karaen Senthilkumar, Suman Raj, Maxime Gonthier 等

★★★★★ 值得关注
arXiv cs.IT · math.IT

Fisher Information and the Minimum Mean-Square Error for Locating Closely Spaced Point Sources

说明近距离点源定位的费舍尔信息与最小均方误差

简介本文研究从带未知复系数的已知平滑响应叠加且含噪声的观测中,定位距离很近的多个点源时,平均误差可以达到的最优界。相位关系使局部费舍尔信息不足以决定可达误差,作者为每个固定源数 K≥2 给出在小间距与各噪声水平下匹配的贝叶斯风险界,并证明投影最小二乘估计量可以达到这些阶数。

看点证明了闭合间距点源定位的贝叶斯风险匹配上下界,并区分奇偶源数的不同风险区间,理论改进明显;影响主要限于信号处理子领域。

Chuling Wen, Jian Lu, Qingtang Jiang 等

arXiv cs.GT

Differentiable Combinatorial Auction Design: Optimizing Revenue-Welfare-Fairness Frontiers With Graph Attention Networks

说明可微分组合拍卖设计:用图注意力网络优化收入、福利与公平的权衡前沿

简介本文提出一个可微分、考虑约束的组合拍卖设计框架,通过端到端学习得到近似策略证明、满足分数可行性的机制,用于机场时段等公共基础设施的分配。作者提出图结构模型CAGraph,并以CANet和CAFormer作为深度学习基线,同时给出把分数分配映射为离散可行分配的分解方法。在合成基准和机场时段剥离案例中,学习得到的机制相比VCG分别获得最高73.5%和180%的期望收入提升,遗憾值较小。

Mai Pham, Vikrant Vaze, Peter Chin

arXiv cs.GT

Randomization to Balance Performance under Nominal and Compromised Communication

说明在通信正常与受损时平衡性能的随机化方法

简介论文研究多智能体系统中,在智能体之间通信正常或受损两种情形下,如何通过让智能体随机选择动作来平衡系统性能。作者证明,对任意场景存在一个随机化程度,使正常通信下的效率接近最优,同时受损通信下的效率仍为严格正值。当智能体需要在越来越多的资源之间选择时,该保证会减弱。

Colton Hill, Brandon Collins, Philip N. Brown

arXiv cs.IT · math.IT

The permutation and automorphism groups of univariate multiplicity codes

说明单变量重数码的置换群与自同构群

简介本文给出了单变量重数码在置换和线性等距变换下保持不变的显式刻画。研究考虑有限域中的任意求值子集、任意重数与维数,自同构以 NRT 度量为准。重数为一时,结果与经典 Reed-Solomon 码在 Hamming 度量下的结论一致;在主要维数范围内,自同构由置换求值子集的射影变换唯一确定。

Eduardo Camps Moreno, Hiram H. L\'opez, Umberto Mart\'inez-Pe\~{n}as 等

arXiv cs.DC

KVStream: Adaptive Parallel Storage Management for KV Caching in Large-Scale LLM Serving

说明KVStream:面向大规模大模型服务的KV缓存自适应并行存储管理

简介长上下文大模型服务中,前缀的KV缓存常超出GPU和主机内存,检索它会占用推理的存储I/O。本文把前缀检索视为跨存储层的聚合带宽调度问题,提出KVStream引擎:批量读取、延迟写入、在各层复制数据块,并让空闲的存储层自适应地领取未读数据块。作者接入LMCache,在四个模型、六个数据集和最多128块GPU上评估,检索速度接近理论带宽上限,离线吞吐最高提升1.49倍,突发请求下平均首token时间最多降低6.1倍。

Avinash Maurya, Jaiaid Mobin, Jie Ye 等

arXiv cs.IT · cs.NI · math.IT

Stochastic Geometry Meets Optimization: Data-Driven Cellular Planning

说明随机几何遇上优化:数据驱动的蜂窝网络规划

简介本文提出一种数据驱动的随机几何方法,用于规划基站部署密度。方法以未知用户位置分布的样本为输入,以最大化网络覆盖等性能指标为目标,并以非齐次泊松点过程进行覆盖分析。作者对离散化与采样误差进行了刻画,并使用随机镜像上升法求解经验问题。数值实验采用合成数据和真实空间需求数据进行验证。

Abhishek K. Shukla, Abhishek K. Gupta, and Ketan Rajawat

★★★★☆ 值得关注
arXiv cs.IT · math.IT

The Cheng-Murray Conjecture on Deep Holes of Full-Length Reed-Solomon Codes

说明全长里德-所罗门码深洞的Cheng-Murray猜想

简介该论文讨论全长里德-所罗门码中的深洞问题:插值多项式次数等于码维数的接收字即为深洞。作者证明,在有限域上3≤k≤⌊q/2⌋的范围内,Cheng-Murray猜想成立,从而完成了所有非例外维数下的分类。证明结合了标记弧的切包络与局部校验子相容性等方法。

看点解决了沿用多年的Cheng-Murray猜想剩余情形,结合切包络与局部综合征相容性等新工具给出完整证明,对子领域影响较大。

Weijun Fang

arXiv cs.IT · math.IT · math.PR

Improved Bounds for the Entropic Central Limit Theorem in the Log-Concave Case

说明对数凹情形下熵中心极限定理的改进界

简介本文研究对数凹各向同性概率测度的独立随机向量归一化和的分布与高斯分布之间的相对熵。作者给出了新的上界,把维数的多项式依赖改进为多对数依赖。证明结合了De Bruijn恒等式与Eldan的随机局部化过程。

Tom Maitre (LMA (Poitiers))

★★★★☆ 值得关注
arXiv cs.IT · math.CO · math.IT

Deep holes of full-length Reed--Solomon codes: uniform bounds and exact classifications

说明全长Reed–Solomon码的深洞:统一界与精确分类

简介该论文研究全长Reed–Solomon码RS_q(k)中插值多项式次数为k+m的深洞,对m=3至7在任意有限域上给出完整分类。结果显示奇数m在此范围内无深洞;m=4与m=6时仅有Segre六次族和Frobenius幂族两类例外,且只出现在特征2的二维情形。文中还给出了任意m≥3的统一界。

看点对全长RS码深洞给出m=3至7的完整分类及一致界,并以严格证明与确定性计算验证,理论推进显著但影响局限于编码理论子领域。

Xiang Fan

arXiv cs.SE · cs.DC · cs.PF

Procrustes-Bering-Sheaft: Automated Model Discovery and Virtual Crash Tests for Microservices

说明Procrustes-Bering-Sheaft:微服务的自动化模型发现与虚拟崩溃测试

简介该论文提出一套工具链,用于微服务的轻量级模型发现和虚拟崩溃测试,通过蒙特卡洛采样估计服务及通信故障下的操作可用性。工具链包括检查部署与追踪证据的Procrustes、发现依赖并纳入副本声明的Bering,以及评估操作成功条件的Sheaft。论文在一个HTTP操作上演示了该流程,并以解析预言和受控测试验证实现。

Anatoly A. Krasnovsky

arXiv math.OC · cs.GT · econ.TH

A Resource Allocation Tournament

说明资源分配锦标赛:多方在多场对局中分配有限资源的竞赛模型

简介论文提出并分析了一种循环赛式的同时资源分配竞赛,参赛者需预先把有限资源分配到与各对手的对局中,结果由相对分配决定。研究比较了总积分与赢家通吃两种计分方式:三人情形给出完整均衡刻画;四人及以上,总积分方式存在Blotto型均衡,赢家通吃则需借助数值与算法分析,作者为此设计了带随机惯性的最佳响应动态算法,并用于近似四人与五人博弈的均衡。

Adam Nathaniel, Refael Hassin