跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1084新增论文
+883其中 AI 相关
+130已有论文修订
+94新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-18 19:45各信源进度 →

统计口径与数据新鲜度

统计 2026-11-18 06:42 — 2026-11-19 06:42(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 19:45库内论文最新更新时间:2026-11-18 08:00

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

26,870 已收录论文22,374 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
版本更新 · v2arXiv:2611.09183

On derandomizing the line-point low-degree test

Prahladh Harsha, Swastik Kopparty, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

原文摘要

We investigate the derandomized version of the classical line-point low-degree test in the high-error regime in the bivariate setting and reveal some unexpected behavior. The classical line-point low-degree test takes an $m$-variate function $f$ over a finite field $\mathbb{F}_q$, queries it along a random line and accepts if the restriction of the function to this line is a low-degree polynomial. The high-error version of (the analysis of) this test asserts that if $f$ has at least $ε$ expected local agreement with a degree-$k$ univariate polynomial on a random line, then in fact $f$ is non-trivially close to some degree-$k$ $m$-variate polynomial even as $ε$ approaches $0$ (provided $q$ is sufficiently large compared to $k$ and $1/ε$). The derandomized version of the problem asks if the same holds when the line is not chosen uniformly over all possible lines but rather from a small set. In this paper we explore the bivariate case ($m=2$). We show, somewhat surprisingly, that there exists a function $f\colon \mathbb{F}_q^2 \to \mathbb{F}_q$ and a set of lines $\mathcal{L}$ in $\mathbb{F}_q^2$ of size nearly $q^{3/2}$ such that on every line in $\mathcal{L}$, $f$ has agreement $\approx 1/2$ on average with some univariate polynomial of degree $k=\sqrt{q}/2$ and yet $f$ is $1 - O(q^{-1/2})$ far from every polynomial of degree $O(k)$. On the positive side, we show that once the field size $q$ is at least $k^2/(ε)^{O(1)}$ such examples disappear and we can get sets of lines of size $O(q/ε^{O(1)})$ on which the low-degree test has a high-error analysis. On the way to our positive result, we show a new high-degree version of the classical two-direction Polishchuk--Spielman divisibility lemma.

cs.CC · cs.IT