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

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

arXiv cs.IT · eess.SP · math.IT

FTN Signaling: Spectral Efficiency from BPSK to 16-QAM

说明FTN信令:从BPSK到16-QAM的频谱效率研究

简介本文研究快于奈奎斯特(FTN)信令在BPSK、QPSK和16-QAM下的有限字符集可达信息速率,采用发射功率约束和MMSE信道缩短检测框架。结果显示,低阶星座可承受更激进的时间加速,高阶星座则在接近奈奎斯特极限时频谱效率最佳。在6 dB参考信噪比下,最优加速因子从BPSK的约0.65变为QPSK的0.75和16-QAM的0.90。

Emre Cerci, Adem Cicek, Melda Yuksel 等

arXiv cs.IT · math.IT

An Improved Upper Bound on the Capacity of the Primitive Diamond Relay Channel

说明原始菱形中继信道容量的改进上界

简介本文研究原始菱形中继信道(primitive diamond relay channel)的容量,利用Csiszár–Körner–Marton和等式及Gallager型识别方法,得到比现有上界更紧的上界。对于高斯原始菱形中继信道,所提上界与Wu、Özgür、Peleg和Shamai提出的强化高斯上界一致。对于离散无记忆信道,该上界在若干信道实例中严格优于割集界和现有上界。

Deniz G\"und\"uz, Yanxiao Liu, Yi Liu

arXiv cs.IT · math.IT

Thresholds for Local Coordinate-Wise Linear Properties of Random One-Point AG Codes

说明随机单点代数几何码的局部坐标线性性质阈值

简介该论文研究随机单点代数几何(AG)码的局部坐标线性(LCL)性质,证明在明确的字母表与采样条件下,它们与随机线性码具有相同的阈值速率。论文还指出此前随机Reed-Solomon码“以上阈值”证明中的概率比较方向有误,并给出新的论证。结果由此得到随机单点AG码在列表解码、列表恢复等方面的新保证,以及多项式曲线上的相关一致性和邻近间隙结果。

Chen Yuan, Ruiqi Zhu

arXiv cs.IT · math.IT

Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem

说明离散Wyner–Ziv问题的精确二阶渐近分析

简介本文重新研究离散Wyner–Ziv问题并给出精确的二阶渐近结果。作者通过后验分解、集中不等式和鞅的条件高斯近似得到二阶逆定理,并将Li与Li(arXiv 2025)的可达性结果推广为允许测试信道依赖于观测源序列的类型。结合两方面的界,得到精确的二阶渐近。对二元非对称源和四元源的数值例子显示,前者中Li与Li的可达界已是最优的,后者中本文的可达结果更优,在超额失真概率为0.1和0.2时分别将二阶编码速率降低10.77%和21.35%。

Lin Zhou

arXiv cs.IT · math.IT

Estimation with Quantized Parameter Side-Information

说明带量化参数侧信息的估计问题

简介本文研究一类参数估计问题,估计器除独立同分布观测外,还能拿到参数的量化版本,且量化等级数有限、但量化方式可以优化。文中给出了该问题极小极大风险的上界与下界,两者在观测样本数和量化等级数都很大时具有相似的衰减速率。

Mathis Wetterwald, Ofer Shayevitz, Mich\`ele Wigger

arXiv cs.DC

Capturing a Moving Target on Star Graphs by Two Communicating Mobile Agents

说明两个可通信移动机器人在星形图上捕获移动目标

简介本文研究在m条射线组成的星形图上搜索移动目标的问题,相当于把线性搜索推广到多个方向。目标由对手放置在某条射线上,并以恒定速度移动。作者考察两个机器人协作的情形,比较面对面通信与收发式非对称通信两种模型,并在三种已知条件下给出竞争比的上界,部分情况还给出下界。

Khaled Jawhar, Evangelos Kranakis

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

Covering radius of rank-metric codes via covering lifts and clubs

说明基于覆盖提升与俱乐部的秩度量码覆盖半径研究

简介本文提出一种基于生成矩阵的几何方法,研究有限域上线性秩度量码的覆盖半径。通过由码的q系统定义的覆盖提升,覆盖半径可由其超平面权重得出,并给出覆盖半径取最大值的精确判据以及其余情形的上界。论文还针对一维码给出具体结论,并确定了m∈{3,4,5}时所有一维码的覆盖半径。

Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco

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

Breaking linearity in the sum-rank metric: MSRD codes from switched σ-rational normal curves

说明打破秩度量中的线性:由切换 σ-有理正规曲线构造的 MSRD 码

简介本文构造了一族标量封闭、非可加的最大和秩距离码(MSRD),方法是切换 σ-有理正规曲线的范数分量,并通过线性化 Reed–Solomon 伴随映射提升点集。对满足特定条件(条件 (◇))的划分,可得到码长为 N、最小和秩距离为 δ 的码,且保留曲线分量时该码非可加。

Daniele Bartoli, Giovanni Giuseppe Grimaldi, Giovanni Longobardi

arXiv cs.DC · cs.SE

NosRacer: Dynamic Detection of Race Conditions in On-Device Network Operating Systems

说明NosRacer:在设备端网络操作系统中动态检测竞态条件的框架

简介论文提出 NosRacer,一种用于工业级设备端网络操作系统(NOS)的竞态条件动态检测框架。该框架分为两个阶段:集中阶段利用配置更新任务的局部性缩小分析范围,扰动阶段主动扰动异步消息的到达顺序,以更容易触发暴露竞态的执行路径。作者在一款商用 NOS 的 5 个关键控制面组件中进行了测试。

Runze Wu, Jingbo Zhai, Shanming Ping 等

arXiv cs.DC

Federated Zeroth-Order Optimization with Direction Aggregation and Variance Reduction

说明基于方向聚合与方差缩减的联邦零阶优化

简介本文研究联邦场景下带约束的非光滑非凸随机优化问题,客户端只能获取随机函数值。作者提出基于方向聚合的联邦零阶框架,并配备两种本地采样方案:FedZOO 用多个球面查询共享的小批量构造本地方向,FedVRZO 则用独立的样本-方向对构造估计量。两者均在服务器端执行一次加权聚合的投影更新,并分别给出收敛性保证,黑盒对抗攻击实验验证了方法的有效性。

Qianlong Dang, Baosheng Li

arXiv cs.DC

New Contraction Bounds for Multidimensional Asymptotic Consensus in Dynamic Networks

说明动态网络中多维渐近共识的新收缩率界

简介该论文研究动态网络中多维渐近一致性问题,节点需收敛到彼此输入的任意近处并保持在凸包内。作者提出非分裂网络模型下收缩率的新上界 √(2d/(3d+1)),并基于 BallMidpoint 算法给出改进结果。论文还给出了多维下界,并指出 BallMidpoint 策略在单轮意义上渐近最优。

Zeremonienmeister Berber Aab, Darya Melnyk, Stefan Schmid

arXiv cs.IT · math.IT

WZIP and WLZ4: LZ77 Codecs with Match-Length-Dependent Sliding Windows

说明WZIP 与 WLZ4:按匹配长度划分滑动窗口的 LZ77 编解码器

简介本文提出两种 LZ77 压缩格式:WLZ4 是字节对齐的 LZ4 类格式,WZIP 是带熵编码的 Zstandard 类格式。两者让每种匹配长度拥有各自的滑动窗口,解码器可由已解码的长度推断偏移范围。在 Silesia 测试集上,WLZ4 的压缩率比 LZ4HC 最高高出 16%,但解码较慢;WZIP 的压缩率超过 Zstandard 22,其可信解码器速度约为 Zstandard 的 91%。

Yingquan "Cody" Wu

arXiv cs.IT · math.IT

Distributed Constrained Resource Management in 6G Networks: A Scalable Hybrid Model-Learning Framework

说明6G网络中的分布式受约束资源管理:可扩展的混合模型-学习框架

简介该论文面向6G无线网络的无线资源管理问题,提出一种两阶段混合学习框架,并将OFDM领域知识融入多智能体强化学习流程。第一阶段基于信道统计为用户分配满足服务质量要求的最小资源,第二阶段用多智能体系统分配剩余资源以最大化系统吞吐量。仿真结果显示,该方法在50MHz带宽等场景下优于现有基线,吞吐量最高提升40%,约束满足率达100%。

Thang X. Vu, Cuong Le, Symeon Chatzinotas 等

arXiv eess.SP · cs.IT · math.IT

Outage-Aware Robust Sensing for UAV ISAC Systems

说明面向无人机ISAC系统的中断感知鲁棒感知方法

简介本文针对多基站无人机跟踪场景,研究动态遮挡导致感知链路不确定时的功率分配问题。作者提出结合历史感知预测和自适应共形预测集的鲁棒功率分配框架,仅对保留的非中断模式施加跟踪约束,并将全部被遮挡模式视为感知中断单独处理。在多个随机种子的闭环仿真中,该方法可服务时隙的约束违反率为0.01%,功率比保护所有非中断模式减少47.0%。

Qiming Li, Lei Zhang, Haoran Xu 等

arXiv econ.TH · cs.GT

Delegate Pricing to Algorithms: When Slow and Steady Wins the Race

说明把定价交给算法:慢而稳的策略何时胜出

简介本文研究在连续时间定价博弈中,企业如何选择学习算法的学习速率。作者构建了一个元博弈,以学习路径上贴现利润之和衡量收益。结果显示:若阶段博弈具有策略替代性,企业更偏好更快的学习;若具有策略互补性,过快的算法会加速对手反应并压缩过渡期利润。作者证明,即使竞争性价格是阶段博弈的占优策略且收敛有保证,均衡中企业仍会设计较慢的算法。

Galit Ashkenazi-Golan, Edward Plumb, Clemens Possnig 等

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

From an entropic inequality for sums in abelian groups to the theorems of Ruzsa and Plünnecke

说明从阿贝尔群求和的熵不等式到Ruzsa与Plünnecke定理

简介本文给出Plünnecke–Ruzsa不等式(关于有限阿贝尔群子集的和集估计)的一个直接信息论证明。证明依赖于一个通过最大化联合熵得到的初等耦合不等式,无需张量幂或渐近构造。文中还得到Ruzsa的和集三角不等式,并将结果推广到非阿贝尔群。

Chandra Nair, Aref Namayandeh, Zhaobang Zhu

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

Three Improved Lower Bounds for Binary Error-Correcting Codes

说明二进制纠错码的三个改进下界

简介本文给出三组二进制纠错码的显式构造,参数分别为 (n,M,d)=(22,84,9)、(24,196,9) 和 (25,65,11),即码长、码字数和最小距离。由此得到 A_2(22,9)≥84、A_2(24,9)≥196、A_2(25,11)≥65 的下界,分别优于公开表中的 80、192 和 64。作者同时发布了全部码字和穷举验证程序以供独立核验。

看点通过显式构造改进三个二进制码的下界,打破了沿用多年的界限,证据为穷举验证的具体码字,对编码理论子领域有实际价值。

Kazuki Ota, Takayuki Osa, Tatsuya Harada

arXiv cs.IT · math.IT

DRL-Based AoI Minimization for RSMA in Finite-Blocklength MU-MISO

说明基于深度强化学习的有限码长多用户MISO系统RSMA信息时效性最小化

简介该论文研究有限码长(FBL)多用户无线网络中的信息时效(AoI)最小化问题,这类场景适用于短状态更新包的低时延传输。作者提出一种演员-评论家深度强化学习框架,用于学习多用户MISO广播信道中的动态资源分配策略,以优化RSMA的相关参数。仿真结果显示,该方法在多数情况下AoI低于现有基准方法,在低信噪比和短码长下优势更明显;在高信噪比下性能与基准相当,且在线执行时只需一次神经网络前向计算。

Enes Kaya, Mehmet Alp Demircio\u{g}lu, Elif Tugce Ceran 等

arXiv cs.DC

LLM Agents as Resilience Engineers for Scientific Applications

说明LLM智能体作为科学应用的容错工程师

简介本文研究前沿大语言模型编程智能体能否自动为高性能计算科学应用实现检查点/重启(checkpoint/restart)容错机制。作者构建了包含16个MPI应用的基准套件,并采用无人工介入的生成-验证-修订流程进行评估,共产出41个可运行的容错实现。结果显示,当关键状态可见或能通过统一抽象访问时,智能体驱动的容错工程是可行的,但状态模块化和碎片化仍是主要限制。

Hai Duc Nguyen, Tekin Bicer, Kyle Chard 等

arXiv cs.DC

Zepp: Accelerating Distributed MoE Serving under Relaxed Balance Constraints

说明Zepp:在宽松均衡约束下加速分布式 MoE 推理服务

简介论文提出 Zepp 系统,用于加速分布式混合专家(MoE)模型的推理服务。它不再把负载均衡当作优化目标,而是作为约束条件,直接优化节点间的通信瓶颈,并在专家放置、路由和执行三个阶段逐步优化。与七个先进的 MoE 服务系统相比,Zepp 的 MoE 层最高加速 6.68 倍,相对最快的基线几何平均加速 1.86 倍。

Chang Chen, Andrew Yang, Tiancheng Chen 等

arXiv q-bio.NC · cs.IT · math.IT

If the brain were so simple: Information-based drivers of intelligence and their interaction through an n-body-inspired framework

说明如果大脑如此简单:基于信息的智能驱动因素及其在受多体问题启发的框架中的相互作用

简介本文从信息论与算法热力学角度,探讨神经系统如何对不同模式的信息作出响应。作者提出“信息焓”概念,并定义“信息焓势能”(IEP)指标,用于量化信号提升系统信息焓的能力,还提出一个受多体问题启发的可检验框架,用以描述神经系统在高维状态空间中的运动。

Brett J. Kagan, Johnson Zhou, Forough Habibollahi 等

arXiv cs.DC

IAPRepair: In-Network Aggregation Enhanced Proactive Repair for Erasure-Coded Storage System

说明IAPRepair:面向纠删码存储系统、结合网内聚合的主动修复框架

简介纠删码存储能以远低于全副本的存储开销提供容错,但修复丢失或有风险的数据块需要大量跨节点传输。该论文提出IAPRepair,联合规划修复批次、分配重建与替换节点,并对需要重建的数据块有选择地启用网内聚合,以减轻接收端负载。在Tofino可编程交换机和16个存储节点的原型及大规模仿真中,该方法相比所评估的先进方法将修复时间至少缩短47.83%。

Lei Liu, Yong Wang, Junqi Chen 等

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

Optimal Multi-Item Auctions with I.I.D. Values

说明独立同分布估值下的最优多物品拍卖

简介本文研究在占优策略激励相容与事后个体理性约束下,以收益最大化为目标的多物品拍卖。买方估值为可加型,各物品价值独立同分布于同一有限分布。对两点分布,论文给出了显式确定性机制并证明其在所有满足约束的随机机制中最优,同时给出计算最优期望收益的多项式时间算法;对一般有限支撑分布,精确计算最优收益为 #P 难问题。

看点给出两点分布下最优多物品拍卖的显式机制,并证明一般有限支撑下精确求解为#P难,理论结果完整且有新意。

Boyu Liu, Zhengyang Liu, Zihe Wang

★★★★☆ 值得关注
arXiv cond-mat.stat-mech · cs.IT · math-ph

A general framework for crystallization in maximal hard-core models

说明极大硬核模型中结晶现象的一般框架

简介本文研究周期性格点型图上的一般极大硬核模型。作者提出一组统一假设,由此推出Peierls条件和收敛的团簇展开,从而套用Pirogov-Sinai理论的结论。论文验证了多个标准周期格点图例子,证明了高活性和低活性两种情形下的结晶现象,并给出界定相共存区域的活性取值估计。

看点提出统一的体积分配假设框架,证明低活性下也可出现结晶,并覆盖多种周期格点模型,证据为严格的理论证明。

Alexander Barg, Qidong He, Geyang Wang

★★★★☆ 值得关注
arXiv cs.GT

Asymptotically Optimal Public Project Redistribution without Bounded Precision: A Complex-Analytic Proof

说明无界精度下公共项目的渐近最优收入再分配:一个复分析证明

简介本文研究公共项目问题中的最坏情形VCG收入再分配机制设计,目标是尽可能多地返还VCG支付且不出现赤字。先前工作只能在类型为有界公分母有理数的假设下使效率比趋近1,本文去除了这一假设,构造了对任意实数类型均适用的确定性、匿名、策略证明且无赤字的机制,其最坏情形效率比为1-O(1/log log n)。证明核心使用了复分析工具。

看点removes a bounded-precision assumption and achieves 1-O(1/log log n) via a novel complex-analytic proof; impact limited to mechanism design theory.

Mingyu Guo

arXiv cs.IT · math.IT

QoS-Aware Joint Concurrency and HARQ-Limit Design for HARQ-CC-Aided Slow Fluid Antenna Multiple Access

说明面向服务质量的并发数与HARQ上限联合设计:基于HARQ-CC的慢速流体天线多址接入

简介本文研究下行链路中采用Chase合并混合自动重传(HARQ-CC)的慢速流体天线多址接入(sFAMA)。作者提出一种兼顾服务质量的并发用户数U与HARQ传输上限C的联合设计方法,通过两阶段优化先最大化可行并发数,再选取满足中断与平均服务约束的最小C。数值结果与蒙特卡洛仿真吻合,所提自适应设计可支持6个并发用户,高于固定HARQ的FAS(3至5个)和HARQ自适应的固定位置天线(2个)。

Sixu Han, Kai-Kit Wong, Hanjiang Hong 等

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

A G-Invariant Erdős--Hanani Theorem with Applications to Optical Orthogonal and Constant-Weight Codes

说明关于 G 不变 Erdős–Hanani 定理及其在光正交码与常重码中的应用

简介本文研究在置换群 G 作用下的 t-(v,k,1) 填充设计,证明在两个关于 G 的条件下,当点数 v 趋于无穷时,存在自由的 G 不变填充,其区组数渐近达到 (1-o(1))C(v,t)/C(k,t),这是 Erdős–Hanani 定理的 G 不变形式。文章将结果应用于光正交码、多维及特征模式光正交码以及循环与准循环常重码,使 Johnson 界在相应参数下渐近可达,并给出一维之外二维光正交码在每个波长至多一个脉冲时最大规模的渐近值。

看点将Erdős–Hanani定理推广到群不变packing,给出渐近最优的G不变构造,并解决光正交码等问题的渐近最大尺寸,证明完整。

Yeow Meng Chee

arXiv cs.IT · math.IT

Modeling and Performance Evaluation of Distributed Satellite Antennas: Space Is Much Closer Than One Might Think

说明分布式卫星天线建模与性能评估:空间比想象中近得多

简介本文研究由多颗协作卫星组成阵列、合成大口径天线的架构,用于向普通手机提供宽带连接。作者结合球面波与平面波模型、地球曲率等几何因素,量化不同简化假设对吞吐量和中断概率的影响。数值结果显示,基于各卫星局部平面波近似的多天线预编码与球面波参考结果十分接近,而全局平面波近似可能导致严重损失甚至完全中断。

Giacomo Bacci, Riccardo De Gaudenzi, Marco Luise 等

arXiv eess.SP · cs.IT · math.IT

Low-complexity Equalization of Zak-OTFS Via Neumann Series

说明基于诺伊曼级数的 Zak-OTFS 低复杂度均衡方法

简介论文提出一种选取正交载波波形基的通用方法,使基与无线信道的时延、多普勒特性对齐,从而实现低复杂度均衡。作者以卫星通信和地面站到无人机通信两类信道为例说明该方法,并表明其对分数时延和多普勒频移具有鲁棒性。当信道抽头位于所选子群内时,单抽头均衡器即可支持可靠通信。

Vineetha Yogesh, Saif Khan Mohammed, Sandesh Rao Mattu 等

arXiv math.ST · cs.IT · math.IT

On the Impossibility of Estimating the Average Mixing Time

说明论平均混合时间无法估计的情形

简介本文从单条平稳轨迹出发,建立了估计马尔可夫链平均混合时间所需样本量的近似匹配的逆向界。与最坏情形的混合时间不同,平均混合时间在平稳分布下对与平稳分布的全变差距离取平均,因此可能小得多。论文的逆向界刻画了何时估计不可能,并在对数因子范围内与已有的可实现界中的关键依赖关系相匹配,从而为估计平均混合时间提供了近似紧的PAC保证。

Nathan A. Judd, Amedeo Roberto Esposito

★★★★☆ 值得关注
arXiv cs.GT

A Constant-Factor Approximation to Multidimensional Consumer Utility

说明多维消费者效用的常数因子近似

简介本文研究在消费者以不可转移的“苦役”支付的社会服务场景中,如何设计机制最大化消费者效用。作者针对多个单位需求买家和各异物品,证明简单机制可对最优效用给出常数因子近似:一般独立估值下为 5.67+ε,独立同分布时为 2e/(e-1),且机制满足贝叶斯激励相容、事后个体理性并可在多项式时间内计算。

看点解决了效用最大化能否由简单机制达到常数因子近似的未决问题,并给出多维独立价值下的常数近似界,改进了以往对数级差距的结果。

Kira Goldner, Taylor Lundy, Thodoris Tsilivis

arXiv cs.DC

LOCAA: An Agentic System for Automated Lossy Compressor Tuning

说明LOCAA:用于自动调节有损压缩器参数的智能体系统

简介大规模科学模拟产生海量数据,有损压缩可降低存储与数据移动成本,但用户通常只能通过误差界调参,而结果难以预知,往往需要耗时的穷举搜索。本文提出基于大语言模型的智能体 LOCAA,借助工具调用、压缩器感知指导与持久记忆进行闭环搜索,支持用户自定义目标与约束。在三个科学应用、五种压缩器上评测,其固定压缩比搜索所需试验次数少于二分搜索与 FRaZ,在多质量约束的任务中平均试验次数由二分搜索的 61.5 降至 17。

Khondoker Mirazul Mumenin, Dong Dai, Sheng Di 等

arXiv cs.IT · math.IT

Polarforming for MIMO Covert Communications

说明面向MIMO隐蔽通信的极化成形方法

简介本文研究基于极化可重构天线的多输入多输出隐蔽通信,发送端和接收端分别进行极化成形,同时优化发射协方差矩阵及收发相位,在隐蔽性与发射功率约束下最大化接收方可达速率。论文推导了窃听方的最优辐射检测阈值与有限观测长度下的最小检测错误概率,并提出带有广义注水更新的交替优化算法。数值结果验证了分析并显示相比基准方案速率最多提高53.8%。

Xin Xie, Jinpeng Xu, Yihang Huang 等

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

Risk-minimizing GUE-implementations of truthful reporting in a Dynamic Social Choice Problem

说明动态社会选择问题中实现说真话的风险最小化GUE机制

简介本文研究动态社会选择问题中的保证效用机制(GUM)。作者证明该机制与风险最小化存在此前未知的联系。在固定有效决策策略的前提下,论文考察了在实现说真话的GUE机制类中方差最小化且预算平衡的转移规则。

Endre Cs\'oka, M\'at\'e Viczi\'an

arXiv cs.AR · cs.DC

SUSpMV: A High Frequency Sparse Matrix Vector Multiplier on HBM Enabled FPGA written in SUS

说明SUSpMV:用 SUS 编写、部署在 HBM 型 FPGA 上的高频稀疏矩阵向量乘法加速器

简介本文介绍 SUSpMV,一种用新兴硬件描述语言 SUS 编写的稀疏矩阵向量乘法(SpMV)加速器,运行于 Alveo U280 FPGA 上。设计使用全部 32 个 HBM 通道,在 400MHz 下向 32 个计算单元流式输入矩阵数据,并以 DDR 存放输入输出向量。原文报告,与同一平台上的已有工作相比,几何平均提升 79%,峰值吞吐量达 144.9 GFLOPs,为理论值的 94%。

Lennart Van Hirtum, David Volz, Andreas Koch 等

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

Settling the Sample Complexity of Rényi Entropy Estimation

说明完成 Rényi 熵估计的样本复杂度刻画(非整数阶)

简介该论文研究在字母表大小为 d 的未知离散分布上,估计非整数阶 α>0 的 Rényi 熵、使加性误差不超过 ε 所需的样本数。作者给出了紧的 Θ 界,补全了此前只解决整数阶情形的复杂度图景。上界通过对大概率项使用改进的多项式逼近估计器降低偏差,下界则采用新的矩匹配构造的困难实例。

看点完整刻画了非整数阶Rényi熵估计的样本复杂度,给出匹配的上下界并提出新的矩匹配构造,证明严格完整。

Qisheng Wang

arXiv cs.DC

Efficient Heuristics and Machine Learning Approach for Fault Characterization in Distributed Self-Stabilizing Programs

说明自稳定分布式程序中故障特征分析的高效启发式与机器学习方法

简介本文研究分布式共享内存系统中的一类一致性违例故障(cvf),即进程读到其他进程写入的过期数据。作者针对(Δ+1)图着色程序提出基于冲突边的状态空间探索算法,并针对最大独立集程序提出机器学习模型,以分析此类故障何时、何处出现,从而改进计算效率。

Amit Garu, Duong Nguyen

★★★★☆ 值得关注
arXiv cs.GT

Settling PROPm and PROPavg in Graphical Resource Allocation

说明图资源分配中 PROPm 与 PROPavg 的判定:证明 PROPm 方向总能存在,PROPavg 可能无解

简介该论文研究图结构下的资源分配公平性:智能体为顶点,不可分割物品为边,每件物品须分给其两端之一。作者证明在多重图上,物品(goods)的 PROPm 分配方向总是存在且可高效计算,该结论也推广到家务(chores)及混合情形。与之相对,即使是带二元估值的简单图,PROPavg 方向也可能不存在,判定其存在性是 NP 完全问题。论文还给出物品情形下 PROPm 的效率损失恰为 2,并给出 PROPm 下福利最优化及 PROPm 与帕累托最优同时成立的硬度结果。

看点解决了PROPm与PROPavg存在性的公开问题,并给出多项式时间构造与NP完全性证明,证明完整严格。

Bo Li, Ankang Sun, Ruijie Wang

arXiv eess.SP · cs.IT · math.IT

Antenna Coding by Pixel Antennas: Unlocking A New Dimension for Wireless Communications

说明像素天线编码:为无线通信开启新的自由度维度

简介传统无线通信天线的辐射方向图是固定的,单靠增加天线数量会受到成本和尺寸的限制。该文综述了利用像素天线进行天线编码的方法:像素天线通过控制相邻像素之间的可变集总元件来调整辐射方向图,从而在波束空间域中提供新的自由度。文章介绍了天线编码的概念与分类,重点讨论了信道增益和复用增益两种提升效果,并梳理了天线编码设计的优化方法,最后概述了相关挑战与机遇。

Zixiang Han, Shanpu Shen, Yifei Yuan 等

arXiv cs.GT

Sharper bounds on the thresholds for sensitive and Blackwell optimality

说明关于敏感最优与 Blackwell 最优阈值的更紧界

简介本文研究完全信息双人随机博弈中的 Blackwell 最优与敏感最优,这两种准则是均值收益最优与折扣最优的推广,能体现更具远见的偏好。作者给出了 Blackwell 阈值与 d 敏感阈值的界,即折扣最优策略与相应最优策略重合所需的最小折扣因子。通过关注“约化”多项式族,结果比已有工作更紧,并借助 Mahler 和 Cauchy 界的根分离方法得到了文献中关于 Blackwell 阈值目前最强的上下界,同时首次给出多链随机情形下 d 敏感阈值的界。

Xavier Allamigeon, St\'ephane Gaubert, Julien Grand-Cl\'ement 等

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

MacKay-Neal Codes Achieve Capacity under MAP Decoding

说明MacKay-Neal码在MAP译码下可达信道容量

简介该论文针对固定度数的MacKay-Neal码,证明了统计力学预测的容量可达性结论。对于每个容量严格大于3/ℓ的二进制输入无记忆对称信道,在最大后验概率(MAP)译码下,平均分组错误概率为O(log N/N),实际传输码率收敛于3/ℓ。

看点证明了统计力学预测的MacKay-Neal码在固定度数下达到信道容量,并给出MAP译码下的显式误差界,属于突出的理论结果,影响主要限于编码理论子领域。

Kenta Kasai

arXiv cs.GT

Asymptotic Subsidies for Envy-Free Allocation

说明面向无嫉妒分配的渐近补贴研究:在不可分割物品分配中,使分配结果做到无嫉妒所需的最小货币补贴的渐近规律

简介该论文研究把m_n个不可分割物品分配给n个代理人时,实现精确无嫉妒所需的最小货币补贴。估值为可加且服从独立同分布,并在n趋于无穷的设定下分情况讨论。文中给出一个三次时间算法,可对每个实例返回无嫉妒结果,并在随机模型下给出补贴的渐近界。对于m_n=qn且q=1的平方情形,文中指出最小补贴为Θ_p(log n)。

Zekai Wu

arXiv cs.IT · math.IT

q-ary GRAND

说明q 元 GRAND(猜测随机加性噪声解码)

简介本文提出适用于 q 元字母表上线性码的 q 元 GRAND 解码器。解码器基于排序后的符号似然数组,用三条局部子节点生成规则产生符号偏差模式。作者证明这些规则可构成全行索引空间上的单调有根生成树,因此在搜索不受限时,最佳优先遍历可实现最大似然(ML)解码。Reed-Solomon 码的仿真验证了与最大似然解码结果一致,并展示了有限搜索预算下的性能与复杂度权衡。

Reza Dianat, Majid Nasiri Khormuji, Hiroyuki Seki

arXiv cs.IT · math.IT

Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage

说明多合谋服务器下基于顺序随机抽样的DNA数据存储隐私检索

简介本文研究DNA数据存储中的顺序随机抽样隐私信息检索(SRS DNA PIR),数据库被均分到多个可能合谋的随机抽样服务器上。作者分析了下载开销(期望查询次数)与隐私泄露(以互信息度量)之间的权衡,并推导出包括一个优化问题形式在内的下界。当每台服务器存储两个文件时该下界可达,作者构造了相应方案;对于任意规模的服务器,则提出在随机选取的服务器子集上应用单服务器方案的构造。

Chen Wang, Natalia Silberstein, Eitan Yaakobi