跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1865新增论文
+1473其中 AI 相关
+176已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-17 04:58 · 全站最近入库:2026-11-17 17:12各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 17:12库内论文最新更新时间:2026-11-17 02:59

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

25,692 已收录论文21,414 AI 相关7,613 有修订112 HF 社区发现

浏览论文库

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

找到 5 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
新论文 · v1arXiv:2611.21299

Turing Agent: Agentic Formal Verification for Mathematical Research

Yang Chen, Qianyi Wang, Ronghui Yang, Zhanhao Li, Yu Cong, Chen Zhang, Hangfan Zhang, Shao Zhang 等 16 位作者

原文摘要

Large language models (LLMs) are rapidly advancing mathematical discovery, moving beyond benchmark-level problem solving to tackle frontier research problems. This progress is ushering mathematics into an era of proof abundance, raising a fundamental challenge: how can we ensure the correctness of the ever-growing volume of AI-generated proofs and transform them into trustworthy, machine-verified mathematical knowledge? We introduce Turing Agent, an agent harness designed to orchestrate end-to-end formal verification of research-level mathematics. Its wo-scale architecture integrates theorem formalization and proof formalization agents, empowered by structured proof decomposition, parallel verification, accumulated proof experience, and selective semantic review. Leveraging our collaborations with theoretical computer science (TCS) researchers, we focus our evaluation on TCS, a particularly demanding domain characterized by intricate quantification, complex dependencies, and stringent semantic requirements. Against direct generation and general-purpose coding harnesses, including Codex CLI and Claude Code, Turing Agent achieves approximately 57-62% faithful formalization success on Formal TCS Bench and 83% overall pass@1 on a TCS-focused subset of RLMEval, using GLM-5.3 and DeepSeek-V4-Pro. Notably, Turing Agent, built on DeepSeek, successfully completes the formal verification of three previously unresolved TCS tasks from OpenAI's October 2026 collection. One particularly challenging TCS problem required about a hundred formally verified auxiliary claims. Moreover, by actively exploring and refining the formalization process, Turing Agent can uncover simpler alternative proofs, expose unnecessary dependencies in original proofs, and generate reusable mathematical knowledge as a byproduct of verification.

cs.AI

新论文 · v1arXiv:2611.19447

Cogirth-Strength Ratios and Matroid Rank Reduction

Yu Cong, Chao Xu, Yajie Zhao

原文摘要

In the rank-$p$ reduction problem, we are given a matroid with nonnegative element weights and seek a minimum-weight set of elements whose deletion lowers the rank by at least $p$. For graphic matroids, this is the minimum $(p+1)$-cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum $k$-cut, which relies on the fact that the minimum cut of a graph is at most twice its strength, the value of a maximum fractional packing of spanning trees. We generalize this approach from graphs to matroids. The matroid analogue of the minimum cut is the cogirth, the minimum weight of a cocircuit, and the analogue of graph strength is matroid strength, the value of a maximum fractional packing of bases. We show that if every matroid in a deletion-closed class has cogirth at most $d$ times its strength, then for every $p$, the natural linear programming relaxation of rank-$p$ reduction is within a factor of $d$ of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a $d$-approximation, and an optimal solution can be found deterministically in $n^{(2d-1)p+O(1)}$ time on $n$ elements. For graphs, $d=2$ and our framework specializes to the tree-packing approach. As applications, we bound the cogirth-strength ratio for two broad classes, and both bounds are tight. For quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids, the ratio is at most $2$ for all weights, giving a $2$-approximation and an exact $n^{3p+O(1)}$-time algorithm. For $(k,\ell)$-count matroids of hypergraphs with $0\le \ell\le k$ and edge size at most $s$, the ratio is at most $ks$ under unit weights. This gives a $ks$-approximation and an exact $n^{(2ks-1)p+O(1)}$-time algorithm for unweighted rank-$p$ reduction.

cs.DS

版本更新 · v2arXiv:2609.10255

Sharp Bounds on the Number of Small Cuts

Yu Cong, Chao Xu

原文摘要

A $k$-cut of an undirected graph is a minimal edge set whose removal leaves at least $k$ connected components, and its cost is the sum of its edge costs. Write $λ_k$ for the minimum cost of a $k$-cut. For fixed $k\ge2$ and $α\ge1$, we show that in any $n$-vertex graph with $n\ge k$ and nonnegative edge costs, the number of $k$-cuts of cost strictly below $αλ_k$ is $O(n^{\lceilαk\rceil-1})$. This implies an $O(n^{\lfloorαk\rfloor})$ bound for $k$-cuts of cost at most $αλ_k$, sharpening the $O(n^{αk})$ bound of Gupta, Harris, Lee and Li. For $k=2$, our strict bound resolves a conjecture of Henzinger and Williamson and an open question of Karger. The exponent $\lceilαk\rceil-1$ is optimal for $k$-cuts for every $k\ge2$ and $α>1$.

math.CO · cs.DM

版本更新 · v2arXiv:2604.23334

A Lagrangian Approach to Interdiction of Linear Minimization Problems

Yu Cong, Kangyi Tian

原文摘要

We study budgeted interdiction of linear minimization problems. Given a family of feasible sets, element weights, and deletion costs, the objective is to delete elements within a prescribed budget and minimize the remaining weight of a feasible set. We give an alternative, simpler Lagrangian approach that generalizes the connectivity interdiction framework of Huang, Obscura Acosta, and Yingchareonthawornchai (IPCO' 24). When the interdiction optimum is positive, we show that the optimal Lagrange multiplier gives truncated element weights, in which every feasible set supporting an optimal interdiction solution has weight less than twice the minimum under the truncated weights. We apply the reduction to graph cuts, $k$ cuts, and cocircuits of perturbed graphic matroids. We obtain deterministic fully polynomial-time approximation schemes for graph connectivity interdiction and for cogirth interdiction on perturbed graphic matroids of fixed perturbation rank. For graph connectivity, the running time is $\tilde O(n^3m^2/\varepsilon)$. The $k$-cut application gives a fully polynomial-time randomized approximation scheme.

cs.DS

新论文 · v1arXiv:2610.38396

Destroying Rigidity in the Plane

Yu Cong, Chao Xu, Yajie Zhao

原文摘要

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

cs.DM