跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+979新增论文
+781其中 AI 相关
+119已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-20 08:48 · 全站最近入库:2026-11-20 19:58各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-20 08:48最近发现新增版本:2026-11-20 19:58库内论文最新更新时间:2026-11-20 02:59

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

28,961 已收录论文24,030 AI 相关8,912 有修订112 HF 社区发现

浏览论文库

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

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 08:46(北京时间)
新论文 · v1arXiv:2611.17554

Online Allocation with Differential Privacy

Jianyi Yang, Xingyu Zhou, Mostafa Mushsharat, Shaolei Ren

原文摘要

We study private online allocation problems, where allocation decisions must satisfy differential privacy (DP) to protect sensitive user information while optimizing performance under limited resources. We first formalize differential privacy notions suited to different privacy requirements in online allocation and establish the fundamental performance limits of any algorithm under these definitions. Based on these insights, we propose PPOA, a privacy-preserving meta algorithm for online allocation, and establish sufficient conditions under which PPOA preserves Joint DP (JDP) or Local DP (LDP) while achieving asymptotically near-optimal performance. Building on these conditions, PPOA can be instantiated into a variety of concrete algorithms. In particular, we present the specific designs, which include PPOA-DMD that preserves JDP and LDP and PPOA-FTRL that preserves JDP. We analyze their performance under both adversarial and stochastic settings and characterize the fundamental trade-offs between DP and allocation performance. Finally, we demonstrate the superior performance of the proposed algorithms via numerical experiments on AI model routing in battery-powered edge systems.

cs.CR

新论文 · v1arXiv:2611.06751

A Quantum Lower Bound for Triangle Finding

Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou

原文摘要

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

quant-ph · cs.DS

新论文 · v1arXiv:2611.05356

突破图碰撞问题的量子查询壁垒

Breaking the quantum barriers for Graph Collision

Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou

AI 速读 基于摘要

作者报告了针对图碰撞问题的改进量子查询算法,推翻此前猜想的 Ω(n^{2/3}) 下界,并给出新的量子查询下界。

quant-ph · cs.CC · cs.DS

查看原文摘要

In the graph collision problem, the task is to decide whether a known graph on $n$ vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured $Ω(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $\widetilde O(n^{92/139})$ queries. We then refine this approach to obtain a $\widetilde O(n^{11/17})$ query algorithm. We also obtain a $\widetilde O((nq)^{11/17})$ query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size $q$, contrasting a known $Ω(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $Ω(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.