跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

arXiv 最近完成扫描:2026-11-22 21:02 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

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

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

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

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

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

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-22 21:00(北京时间)
版本更新 · v2arXiv:2610.36691

自适应相干性的差分隐私预处理幂迭代主成分分析方法

Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence

Duy V. Le, Ta Duy Nguyen, Alina Ene, Huy L. Nguyen

AI 速读 基于摘要

提出一种基于预处理幂迭代的差分隐私PCA算法,其效用保证随输入矩阵的相干性提高而改善。

cs.DS

查看原文摘要

In Principal Component Analysis (PCA), we are given as input a matrix $A\in\mathbb{R}^{n\times d}$ and an integer $k\leq d$, and the goal is to find the top $k$ right-singular vectors of $A$. We consider the setting where each row of $A$ is the private data of an individual, and we design an $(ε,δ)$-differentially private algorithm whose utility guarantee improves with the coherence of the input matrix. Prior works were either restricted to the case $k=1$ or ensured significantly weaker privacy protections. Our algorithm is based on a preconditioned variant of the power iteration method that is designed to significantly reduce the noise needed to ensure privacy.

版本更新 · v4arXiv:2602.11454

Adaptive Power Iteration Method for Differentially Private PCA

Ta Duy Nguyen, Alina Ene, Huy Le Nguyen

原文摘要

We study $\left(ε,δ\right)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a data point in $\mathbb{R}^{d}$. Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.

cs.DS · cs.LG

新论文 · v1arXiv:2611.15822

A Faster Scaling Algorithm for Maximum Weight Matroid Intersection

Alina Ene, Huy L. Nguyen

原文摘要

We consider the maximum weight matroid intersection problem. In this problem, we are given two matroids $M_{1}=(E,\mathcal{I}_{1})$ and $M_{2}=(E,\mathcal{I}_{2})$ and integer weights $w(e)$ on the elements $e\in E$, and the goal is to find a maximum-weight common independent set. We give a randomized algorithm that constructs an optimal solution using $\widetilde{O}(nr\log W)$ queries to the independence oracles of the matroids, where $n$ is the size of the ground set $E$, $r$ is the minimum rank of the two matroids, and $W$ is the maximum weight.

cs.DS

版本更新 · v2arXiv:2610.25403

A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

Alina Ene, Huy L. Nguyen

原文摘要

We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee, Sidford, and Wong (FOCS 2015), Dadush, Végh, and Zambelli (SODA 2018), and Jiang, Lee, Song, and Zhang (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Iwata, Fleischer, and Fujishige (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.

cs.DS