跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文，不再错过。

覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。

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

全站更新概况

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

arXiv 最近完成扫描：2026-11-08 23:55 · 全站最近入库：2026-11-08 06:02各信源进度 →

统计口径与数据新鲜度

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

最近完成检查：2026-11-08 23:55最近发现新增版本：2026-11-08 06:02库内论文最新更新时间：2026-11-06 02:59

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

17,100 已收录论文14,661 AI 相关4,057 有修订112 HF 社区发现

浏览论文库

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

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

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-08 23:54（北京时间）
版本更新 · v2arXiv:2609.08259

Stable Voting Rules on the Edge of Optimal Metric Distortion

Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang, Qilin Ye

原文摘要

We prove the existence of a randomized voting rule with metric distortion at most $2.1248$, within $0.013$ of the lower bound of $2.11264$. Our rule comes from a generalization of \emph{stable $k$-lotteries} developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries. In particular we show that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates, and that stable $2$-lotteries are optimal in this class of voting rules.

cs.GT

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

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

Ziyi Cai, Shuangping Li, Yiheng Shen, Kangning Wang, Peng Zhang

原文摘要

Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.

cs.DS · cs.AI · cs.CL · cs.DM · cs.LG

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

Spectrum Is Not Enough: A Random-Matrix Account of Data-Free Preconditioning for Differentially Private Learning

Shilin Zhang, Kangning Wang

原文摘要

At a fixed privacy budget, curvature is exactly the object the budget makes unavailable. A recent answer estimates it from synthetic probes, at neither privacy cost nor distribution shift, and validates a probe by the eigenvalue decay it reproduces. That test reads the spectrum, not the basis, and what a probe reconstructs is unknown. This paper gives a random-matrix account of data-free preconditioning, organized by one dichotomy. Of the two Kronecker factors, the error-signal factor $ G $ and the architecture-determined bulk of the activation factor $ A $ are reconstructible without data up to an explicit error-energy bound; only the data-induced spikes of $ A $ are not. We verify that bound with zero violations along a full training trajectory, though it stays one to nearly three orders of magnitude above the gap it bounds. We locate the failure boundary at a Baik-Ben Arous-Péché threshold: a bulk-only probe suffers an exact damage $s^2/(1-s^2)$ from a spike of strength $s^2$, invisible once its amplitude exceeds the scaled-bulk threshold $( \sqrt {c}/(1+ \sqrt {c}))^{1/2}$, $c = d/n$. The test in use is basis-blind: rotating only the probe eigenbasis at a near-exact matched spectrum inflates the residual by $2.3 \times $ to $89.8 \times $, and a closed-form volume law fixes the within-spectrum ordering of the critical volume while a two-oracle construction proves that no functional of the probe spectrum fixes its magnitude. Over forty seeds on three modalities, per-layer tuning does not transfer to accuracy, no data-free arm beats the flat probe, public-data curvature does on both modalities tested, and the ordering inverts on PathMNIST under real DP noise. The account yields a probe-design protocol and falsifiable predictions for the regimes where data-free curvature can be trusted.

cs.LG

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

Persuasion by Parts

Shuyuan Jia, Kangning Wang, Renzhe Xu

原文摘要

Classical Bayesian persuasion assumes that an information designer can condition signals on the entire state. We propose persuasion by parts. In this model, the receiver's payoff from acting is $X = \sum_{i=1}^n X_i$ for independent coordinates $X_1,\ldots,X_n$ observed by separate sources. The designer commits in advance to a product experiment, in which each source $i$ can condition its signal only on $X_i$. Given the signals, the receiver computes her posterior mean $y$ of $X$ and acts with probability $g(y)$, where $g\colon \mathbb{R} \to [0,1]$ is a nondecreasing function. The designer aims to maximize the probability of action. Let $V_{\mathrm{prod}}(g)$ and $V_{\mathrm{joint}}(g)$ be the supremum probabilities of action under persuasion by parts and under joint persuasion, respectively. When the designer knows $g$, we show $$ V_{\mathrm{prod}}(g) \;\ge\; c\,V_{\mathrm{joint}}(g)^2 \qquad\text{for every nondecreasing } g\colon \mathbb{R} \to [0,1], $$ where $c > 0$ is an absolute constant independent of $n$ and the prior; the exponent $2$ is tight. When $g$ is unknown, we construct a product experiment $Π$ from the prior alone, whose probability of action $V_Π(g)$ satisfies $$ V_Π(g) \;\ge\; c_\varepsilon\,V_{\mathrm{joint}}(g)^{2 + \varepsilon} \qquad\text{for every } \varepsilon > 0 \text{ and every nondecreasing } g\colon \mathbb{R} \to [0,1], $$ where $c_\varepsilon > 0$ depends only on $\varepsilon$.

cs.GT · econ.TH

查看论文
arXiv ↗PDF ↗