跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+479新增论文
+361其中 AI 相关
+64已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-16 21:56各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-16 21:56库内论文最新更新时间:2026-11-14 02:59

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

23,827 已收录论文19,941 AI 相关6,922 有修订112 HF 社区发现

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
版本更新 · v2arXiv:2609.27932

Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions

Tao Jiang, Minbo Gao, Shaowei Cai

原文摘要

When the weights and biases of a neural network range over a fixed finite alphabet, training the network to fit a data set exactly becomes a finite combinatorial problem, and parameterized complexity asks which structural quantities of an instance make this problem tractable. Ganian, Sommer, and Sorge (ICLR 2026) showed that training quantized networks is fixed-parameter tractable when parameterized jointly by the input dimension $α$, the output dimension $ω$, and the treewidth of the architecture, and they asked whether $α+ω$ alone suffices. We show that it does not: training binary quantized networks is W[1]-hard parameterized by $α+ω$, so it admits no algorithm with running time $f(α+ω)\cdot|I|^{O(1)}$ for any computable $f$ unless FPT = W[1]. Hardness holds already for exact fitting of $k+1$ examples whose inputs equal their targets and form a coordinatewise prefix chain, and also when all biases are fixed to zero. The proof rests on a one-flip routing equivalence. On such data, nonnegative binary weights force every neuron to switch on at most once, and a network fits the data exactly if and only if the architecture contains vertex-disjoint paths that link each changing input to the corresponding output. Every neuron therefore has one of only $k+1$ activation profiles, yet deciding whether these profiles can be realized simultaneously is as hard as disjoint-path routing. Small input and output dimensions thus limit what each neuron can do locally, but not how the architecture forces neurons to share resources globally.

cs.LG

版本更新 · v2arXiv:2607.10697

A Better Analysis For PPSZ For 3-SAT

Tao Jiang, Shaowei Cai

原文摘要

The PPSZ algorithm of Paturi, Pudlák, Saks, and Zane solves 3-SAT by processing the variables in a uniformly random order, setting a variable whenever a bounded number of clauses implies its value, and guessing it otherwise. Its running time is determined by how many variables are forced in this process, and the exact exponent is a central question in the study of exponential-time satisfiability algorithms. Scheder showed that the classical analysis of PPSZ is not tight for 3-SAT. We ask how much further a sharper analysis of the unmodified algorithm can go. Our analysis uses auxiliary distributions on variable orderings that correlate the positions of variables sharing critical clauses. Such correlations make forcing more likely for some variables, can make it less likely for others, and incur an entropy cost. We choose the correlated pairs at random on short components, so that every pair is selected with the same probability, and we express the forcing loss as a sum of weights attached to these pairs in advance. Gains and losses then scale by the same factor and can be compared directly. Combining the resulting estimate with the complementary estimate of Scheder through an explicit linear-programming certificate gives a uniform improvement for every uniquely satisfiable formula. We prove that the original PPSZ algorithm, with a sufficiently large but fixed implication strength, solves Unique-3-SAT in randomized time $O^*(1.306969598^n)$. Through the lifting framework of Scheder and Steinberger, it solves general 3-SAT in randomized time $O^*(1.307031578^n)$. Both bounds improve the guarantees obtained from the analysis of Scheder for the same algorithm. These improvements follow entirely from the analysis, while PPSZ continues to use a uniformly random variable order and unbiased guesses. It shows that the known guarantees for PPSZ can be strengthened by analysis alone.

cs.DS