跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+0新增论文
+0其中 AI 相关
+2已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-15 10:52 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-14 13:09 — 2026-11-15 13:09（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-15 10:52最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

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

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

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

找到 5 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 10:50（北京时间）
版本更新 · v2arXiv:2604.13577

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model

Yuichi Yoshida

原文摘要

We study property testing of directed acyclicity in the unidirectional bounded-degree oracle model, where a query to a vertex reveals its outgoing neighbors. We prove that there exist absolute constants $d_0\in\mathbb{N}$ and $\varepsilon>0$ such that for every constant $d\ge d_0$, any one-sided $\varepsilon$-tester for acyclicity on $n$-vertex digraphs of maximum outdegree at most $d$ requires $\widetildeΩ(n^{2/3})$ queries. This improves the previous $\widetildeΩ(n^{5/9})$ lower bound for one-sided testing of acyclicity in the same model. We also prove that, under the same degree assumption, any two-sided $\varepsilon$-tester requires $Ω(\sqrt n)$ queries, improving the previous $Ω(n^{1/3})$ lower bound. We further prove an $Ω(n)$ lower bound for tolerant testing for some absolute constant outdegree bound $d$ by reduction from bounded-degree $3$-colorability.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.16176

A One-Sided Sublinear-Query Tester for Bounded-Degree 2SAT

Yuichi Yoshida

原文摘要

We give a one-sided tester for satisfiability of 2CNF formulas in the bounded-degree model. For every degree bound $Δ$, distance parameter $\varepsilon>0$, and $ν\in(0,1/2)$, its query complexity on $n$-variable formulas is $\widetilde O_{\varepsilon,Δ,ν}(n^{1/2+ν})$.

cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2604.02582

Sensitivity and Locality Lower Bounds via Low-Soundness Label Cover

Noah Fleming, Max Hopkins, Yuichi Yoshida

原文摘要

We study the sensitivity of approximation algorithms, which measures how much their output distributions change under a single input edit. We show that, for Set Cover, Dominating Set, Min-Rep, and minimum unweighted directed 3-spanner, even a $\log^βn$ approximation requires sensitivity $n^{Ω(1)}$, for some absolute constant $β>0$ and all sufficiently large $n$. The lower bounds hold even for randomized algorithms with unrestricted computation. Here $n$ is the universe size for Set Cover and the number of vertices for the graph problems. On bounded-degree graphs, our sensitivity lower bounds imply logarithmic locality lower bounds in the randomized LOCAL model and its non-signaling generalization. For Dominating Set, fix $\varepsilon\in(0,1)$ and a sufficiently large constant maximum-degree bound $Δ$. A $(1+\varepsilon)\lnΔ$ approximation can be achieved with sensitivity and LOCAL round complexity independent of $n$. We show that improving the ratio to $(1-\varepsilon)\lnΔ$ requires sensitivity $n^{Ω_{\varepsilon,Δ}(1)}$, and hence locality $Ω_{\varepsilon,Δ}(\log n)$. For minimum unweighted directed 3-spanner, every constant approximation factor requires logarithmic locality, even on DAGs of constant maximum total degree. The key ingredient is a polynomial sensitivity lower bound for a variant of low-soundness Label Cover. Fleming and Yoshida established such a lower bound when the required fraction of satisfied constraints on satisfiable instances is close to one. We extend this to inverse-polylogarithmic fractions, enabling the reductions to the problems above. We adapt the Impagliazzo--Kabanets--Wigderson direct-product construction and Dinur--Harsha iterated composition to control the propagation of input edits, and design recovery procedures that are stable under changes to both the supplied labeling and the source instance.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.02374

Submodularity Is Barely Testable

Diptaksho Palit, Yuichi Yoshida

原文摘要

In 2010, Seshadhri and Vondrák asked: is submodularity testable? For functions $f : \{ 0, 1 \}^n \to \mathbb{R}$, they gave a tester that makes $2^{O(\sqrt{n} \log n)}$ queries. We show that every tester, even an adaptive one with two-sided error, must make $2^{Ω(\sqrt{n})}$ queries, thereby concluding: submodularity is barely testable.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2610.36630

Uniformity Testing for the Monomer-Dimer Model

Joy Qiping Yang, Yuichi Yoshida

原文摘要

We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.

cs.DS · cs.DM

查看论文
arXiv ↗PDF ↗