跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

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

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

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

浏览论文库

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

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

找到 9 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 05:40（北京时间）
新论文 · v1arXiv:2611.11701

Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy $k$-$\mathsf{LIN}$ Over Expanders

Riddhi Ghosal, Isaac M Hair, Aayush Jain, Amit Sahai

原文摘要

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming $n^{\log^αn}$ hardness of the standard planted clique conjecture, for any $α\in (0,1)$, and a relatively mild hardness conjecture about noisy $k\mbox{-}\mathsf{LIN}$ over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC'10].

cs.CR

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2608.14529

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

Isaac M Hair, Amit Sahai

原文摘要

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

cs.CC

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

List Recovery for Random Low-Rate Linear Codes

Isaac M Hair, Amit Sahai

原文摘要

We show that random linear codes of fixed dimension $d$ over sufficiently large prime fields have nearly optimal output list size for list recovery. Fix an error fraction $0<α<1$ and $0<\varepsilon<1$. For all sufficiently large block lengths $n$, with probability at least $1-\varepsilon$, the following holds simultaneously for every input list size $\ell\le 2^{δn/\log n}$, where $δ>0$ depends only on $α,\varepsilon$, and $d$. Given any list of $\ell$ symbols at each coordinate, at most $(1+\varepsilon)\ell/(1-α)$ codewords agree with the lists in at least $(1-α)n$ coordinates. Our proof adapts the colored-graph and determinant arguments of Matousek, Privetivy, and Skovron for reconstructing planar point sets from their projections. We also prove that the range of input list sizes is nearly optimal. There is a constant $c=c(α,\varepsilon)>0$ such that, for every linear code of dimension at least two over a sufficiently large prime field $\mathbb{F}_p$ and every $2^{cn}\le\ell\le p$, there are lists of size $\ell$ and a set of more than $(1+\varepsilon)\ell/(1-α)$ codewords, each of which agrees with those lists in every coordinate. The main results of this paper were discovered by ChatGPT 5.5 Sol using harness components from the UCLA Moonshot Harness Project, in response to a less optimal result found by the authors. See the end of the introduction for a discussion.

cs.IT

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

Expanding Codes with Polynomial Stretch

Isaac M Hair, Amit Sahai

原文摘要

We give a polynomial-stretch, constant-arity counterpart to the expanding-code construction of Blasiok, Lou, Rosen, and Sudan (FOCS 2026). For every constant $\varepsilon\in(0,1/2)$, we construct binary matrices with $n$ columns and polynomially many rows, each of weight $k=O(\varepsilon^{-6})$, such that the union of the supports of any set of at most $n^{1-\varepsilon}$ rows has size at least $(1-\varepsilon)k$ times the number of rows. Nevertheless, a polynomial-time test accepts every codeword (generated by the columns of this matrix) corrupted in at most a $1/2-\varepsilon$ fraction of its coordinates, while rejecting a uniformly random vector with high probability. We give two applications. First, we obtain a family of (nearly lossless) constant locality expanders on which Goldreich's pseudorandom generator with the XOR-MAJ predicate can be distinguished from uniform in polynomial time, well within the small-bias parameter regime and the hard regime for known algebraic-immunity/annihilator attacks and algebraic-degree linearization attacks described by Applebaum and Lovett (STOC 2016, SICOMP 2018). Second, we obtain public key encryption from either the constant-noise $k$XOR conjecture over random graphs or the Goldreich conjecture with XOR-MAJ over random graphs, together with a new planted-hypergraph conjecture. We prove low-degree lower bounds for the planting conjecture, providing evidence for subexponential hardness, and give lower bounds against dimension tests based on coordinatewise products (Schur products) of public-code vectors. The PKE schemes and lower bounds were discovered by the authors. The code construction was discovered by Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

cs.CR

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2609.18275

Witness Encryption via Prime-Order Generic Groups

Isaac M Hair, Amit Sahai

原文摘要

For every constant $c > 0$, we unconditionally construct witness encryption for NP in the classical generic cyclic group model with the following properties. For SAT instances of size $n$, encryption runs in time poly$(n)$, and any satisfying assignment can be used to decrypt in poly$(n)$ time with correctness error $2^{-n}$. If no satisfying assignment exists, every generic adversary making at most $n^{(\log n)^c}$ group queries has distinguishing advantage at most $n^{-(\log n)^c}$. Along the way, we give the first superconstant-factor NP-hardness of approximation result for homogeneous MinRank under randomized polynomial-time reductions. We obtain a gap of $(\log n)^c$ for any prescribed constant $c>0$, even when YES instances are required to have a rank-one matrix of the form $\mathbf u\mathbf v^T$ where $\mathbf v$ is a 0/1 vector. The main results of this paper were discovered by Codex / ChatGPT 6 Astra Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy for witness encryption suggested by the authors. See the end of the introduction for a discussion.

cs.CR

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

面向AI辅助数学发现的持续图记忆与社区基础设施

Continual Graph Memory and Community Infrastructure for AI-Assisted Mathematical Discovery

Eric Hanchen Jiang, Junyi Zhang, Jinxi Yu, Jiachen Lu, Zhi Zhang, Michael Simon, Justin Baker, Richard Cai 等 30 位作者

AI 速读 基于摘要

作者提出Ansatz研究框架与Ansatze社区平台，用持续图记忆区分模型接受的结论与人工整理探索，并支持数学研究的检查、引导与形式化验证。

cs.AI · cs.CL

arXiv ↗PDF ↗
查看原文摘要

Mathematical discovery requires preserving partial ideas and the evidence supporting their reuse. We present Ansatz, a research harness whose continual graph memory separates model-accepted claims and dependencies from curated exploration, and Ansatze, a community platform for inspecting, guiding and checking this work. On First Proof, Ansatz recorded nine local verifier closures in each of two ten-problem batches; a partial result in the Second Batch also counted as a pass under the study's criterion. These model-assessed outcomes include continued searches and differ from expert validation. Component studies and re-review expose disagreements and their dependency reach. Open-problem investigations produced candidate results, with five Lean formalizations reported. The platform connects problem discovery, research records, manuscript analysis and formal checking while preserving distinct evidence states. Together, these systems support cumulative human-AI research through persistent investigation and inspectable contributions.

版本更新 · v4arXiv:2607.21551

Unconditional Unclonable Encryption

Prabhanjan Ananth, Seyoon Ragavan, Amit Sahai

原文摘要

We give an unconditional construction of information-theoretically secure one-time private-key unclonable encryption for one-bit messages, with efficient encryption and decryption and exponentially small unclonable-indistinguishability advantage. Previous work by Bhattacharyya and Culf (Nature Physics, 2026) and Bhattacharyya, Broadbent, and Culf (arXiv:2603.08916) either only showed inverse-polynomial security loss or required inefficient encryption/decryption operations; we avoid both of these caveats. Our scheme's key is a uniformly random non-identity phase-free Pauli on $n$ qubits, and bit $a$ is encrypted as a random $(-1)^a$ eigenstate of that Pauli. We prove that the probability that both receivers recover the bit is at most $1/2 + O\left(2^{-n/2}\right).$ By a lower bound due to Broadbent, Culf, and Rochette (IACR Communications in Cryptology, 2026), this is the best probability bound achievable with $n$-qubit ciphertexts while ensuring perfect correctness (up to the constant hidden in the $O(\cdot)$).

quant-ph · cs.CR

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

Does Reasoning Improve Psychological Depth in Large Language Models?

Ruichen Zheng, Yihe Wang, Fabrice Harel-Canada, Sara Khosravi, Zeynep Senahan Yildiz, Amit Sahai, Nanyun Peng

原文摘要

Benchmark gains from reasoning-enhanced large language models encourage the assumption that these models should broadly perform better on complex generative tasks, but this remains underexplored in open-ended, creative domains shaped by nuances of reader experience. We tested this assumption through the lens of psychological depth in short stories. We compared DeepSeek-R1 vs. DeepSeek-V3, our closest available contrast for reasoning-oriented post-training, and GPT-5 vs. GPT-4o, through 60 blinded pairwise evaluations in which seven human annotators and an ensemble LLM-as-a-Judge rated prompt-matched story outputs. Human evaluations showed no universal reasoning advantage: GPT-5 was slightly preferred over GPT-4o (60.0-62.9% across two reasoning-effort settings), whereas DeepSeek-R1 fell behind DeepSeek-V3 (42.9%). Although this pattern was marked by low inter-annotator agreement (Krippendorff's $α= 0.070$), our annotation-quality checks suggested genuine evaluative subjectivity, plausibly reflecting distinct annotator decision schemes rather than annotation failure. In contrast, the LLM-as-a-Judge showed a strong pro-reasoning bias (98.3% of pairs vs. 55.2% of human votes), consistent across its five configurations and partly tracking sentence length. These findings suggest that, at the frontier, reasoning-related quality differences are small enough to be dominated by reader subjectivity, and that LLM-as-a-Judge evaluators can obscure this subjectivity in nuanced creative-generation tasks.

cs.CL

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2607.07779

From Solvers to Research: Large Language Model-Driven Formal Mathematics at the Research Frontier

Eric Jiang, Xiao Liang, Junyi Zhang, Justin Baker, Zhi Zhang, Yingjia Wan, Yubei Li, Jinxi Yu 等 41 位作者

原文摘要

Large language models have made rapid progress in generating machine-checked proofs for well-defined mathematical problems. Extending this progress to research mathematics requires more than solving isolated theorems. Research involves choosing questions, developing definitions and conjectures, connecting results, and combining formal proofs with expert judgment. This survey examines how LLM-driven systems can support these broader activities. We review formal-mathematics tasks, datasets, and autoformalization, and organize proof-generation methods into three overlapping areas: training strategies, inference-time search and adaptation, and agentic workflows. We then examine benchmark results, selected research projects, and platforms for collaborative mathematical work. A central distinction runs throughout the survey: checking a formal proof does not by itself establish that it captures the intended problem or makes a new mathematical contribution. We therefore distinguish theorem benchmarks, repository tasks, formalization projects, and research claims, and discuss the evidence needed to assess each. Finally, we identify five priorities for progress: better data and evaluation, representations of mathematical relationships, conjecture and concept generation, reliable tool integration, and human--AI collaboration. Together, these perspectives connect advances in proof generation to the practical demands of mathematical research.

cs.CL · cs.AI

查看论文
arXiv ↗PDF ↗