跳到正文
arXiv math· Zeev Dvir·· 7 天前精选AI 评分69

实数域上常查询局部可纠码的新构造(预印本)

Constant query LCCs over the reals

AI 导读

一篇 11 页预印本给出了实数域上常查询局部可纠码(LCC)的新构造。此前常查询 LCC 只存在于正特征域,并被猜测在实数域上不存在;该构造利用整数网格上的低次多项式求值,配合一种平滑采样:对给定网格点 P 随机取一条经过 P 的二次曲线,使其与网格相交于多个点作为解码查询,且没有网格点被高概率查询。论文作者标注该构造由 ChatGPT Astra 找到,文中还指出这些查询位置都是附近的网格点。

AI 深度导读基于原文整理的分节解读
背景
常数查询复杂度的局部可纠错码(LCC)此前的构造只存在于正特征域上,并且有猜想认为实数域上不存在这类码。这篇短文要处理的正是实数域上能否构造常数查询 LCC 这一问题。
做法
构造建立在整数网格上的低次多项式求值之上,并配以一个采样程序:给定网格点 P,采样器输出一条经过 P 的随机二次曲线,该曲线与网格相交于许多其他点,这些交点即解码查询位置。采样器具有“平滑”性质,即没有哪个网格点会以高概率被查询。构造出的码还具备额外性质:被查询的位置(曲线与网格的交点)都是附近的网格点。
结论
文中给出了实数域上常数查询 LCC 的一个新构造,其查询次数为常数。所构造的码同时满足两点:平滑采样(单个网格点不会被高概率查询)以及查询位置均为邻近网格点。摘要未给出码长、查询次数、可纠错比例等具体参数。
意义
此前常数查询 LCC 的构造局限于正特征域,且实数域上被猜想不存在;该构造给出了实数域上的一个反例性实例,把这一码类的存在范围扩展到实数。

本页是 AI 精读,不转载论文原文;完整论文(含方法、图表与参考文献)见原文

推荐理由

实数域上此前被认为不存在的常查询局部可纠码被构造出来,给出了具体的多项式求值与采样方法。

来源:arXiv math · arxiv.org