跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

arXiv 最近完成扫描:2026-11-23 01:07 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-23 01:07最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

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

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-23 01:05(北京时间)
新论文 · v1arXiv:2611.01402

Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k

Ziang Ni

原文摘要

We prove that Max-3-Cut is NP-hard to approximate within a factor of $27/29+\varepsilon \approx 0.931$. This improves the factor $16/17 \approx 0.941$ of Austrin, O'Donnell, Tan and Wright, the best NP-hardness result for Max-3-Cut since 2012. (Their result, unlike ours, also holds for 3-colourable graphs.) We also improve the NP-hardness of Max-$k$-Cut for every $k$ from 4 to 20; for instance, we obtain $45/47 \approx 0.957$ for Max-4-Cut and $33/34 \approx 0.971$ for Max-5-Cut, where the previous factors were 0.987 and 120/121. Our reductions are gadget reductions from Håstad's linear equations over $\mathbb{Z}_3$, with gadgets that have at most six auxiliary vertices. The main new idea is a negation trick: since the negation of an assignment is again an assignment, equations with right-hand sides $t$ and $-t$ can be handled together, and this makes the resulting predicates symmetric under all permutations of the colours. We complement it with a general soundness criterion for such reductions: in effect, the best strategy of the adversary is to use a single colour pattern everywhere. This criterion is the strongest analysis that uses Håstad's theorem as a black box, and, using LP duality, we show that under it no gadget reduction from these equations can beat $27/29$ for Max-3-Cut. Finally, we observe that a classical reduction from Max-3-Cut to Max-$k$-Cut, applied more carefully, already gives $82/85 \approx 0.965$ for Max-4-Cut on 4-colourable graphs, improving the previously stated $85/86$.

cs.CC

新论文 · v1arXiv:2610.38015

Measured or Real? When Model-Derived Measurements Can Be Corrected or Compared

Yifeng Li, Ziang Ni

原文摘要

Numbers computed from trained models, such as an example's difficulty or a model's benchmark lead, change with seed and prompt. We ask when such measurements can be corrected or compared. Noise shrinks correlations, and the textbook correction divides by the square root of two estimated reliabilities. On two CIFAR-100 difficulty scores, it returned correlations above one in 70 of 100 classes. We prove that its mean squared error is infinite even when the correlation and the reliabilities use separate seeds. Our rule corrects only when both reliabilities pass a significance test, then divides by their upper confidence bounds. Its output is always bounded, and its coverage guarantees assume Gaussian noise. It helps once reliability is well estimated, more than halving the error with 500 simulated units. Prompt settings can reverse rankings. On ARC, Qwen2-1.5B trails Llama-3.2-3B by 3.8 points with no examples in the prompt and leads by 16.6 with two. Across four benchmarks, averaging the two settings names one winner for 15 of 16 such reversals. We compare models within each setting, controlling family-wise error asymptotically in the number of items for a fixed prompt grid. Aligning embedding coordinates across seeds raises held-out per-dimension reliability from 0.003 to 0.813.

cs.LG · cs.CL