跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

统计 2026-11-20 02:05 — 2026-11-21 02:05(北京时间) · 点击数字查看对应简报;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 社区发现

浏览论文库

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

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

Denoising the US Census: Succinct Block Hierarchical Regression

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon

原文摘要

The 2020 United States Census adopted differential privacy to protect individual confidentiality, adding calibrated noise to summary demographic measurements that are then reconciled into population tables. We developed BlueDown, a postprocessing algorithm that combines techniques from linear regression and constrained optimization while exploiting measurement structure for efficiency. On 2020 Census data, BlueDown reduced the error of groupings by race at the county level by 21-36% and of all county-level groupings by 9-58%; at the tract level, it reduced error of groupings by housing type by 38-61%. These gains came at no cost to confidentiality or computational efficiency, and would improve the validity of research relying on this definitive dataset and analyses used to guide the distribution of over $1.5 trillion in annual federal spending.

cs.LG · cs.CR

版本更新 · v3arXiv:2602.15815

隐私过滤器被残差刻画:自由自然过滤器的特征与自适应性的代价

Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

Matthew Regehr, Bingshan Hu, Ethan Leeman, Pasin Manurangsi, Pierre Tholoniat, Mathias Lécuyer

AI 速读 基于摘要

论文用贝尔曼方程刻画隐私过滤器的最坏情况隐私损失,提出统一现有过滤器的残差过滤器,并研究自然过滤器的自由性与自适应代价。

cs.CR · cs.DS

查看原文摘要

We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We show that the worst-case privacy loss of interacting with any privacy filter is characterized by a Bellman equation. We apply this theory to develop residue filters, which unify existing privacy filters. We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the naïve GDP filter. We show that, in the average case, this new filter asymptotically permits as many pure DP queries as in the non-adaptive case and a factor $π/2$ more pure DP queries than the naïve GDP filter. We also show that residue filters capture the natural filter, which promises greater utility by leveraging exact privacy accounting techniques. Earlier privacy filters consider only simple privacy parameters such as Rényi-DP or GDP parameters. Natural filters account for the entire privacy profile of every query, promising more efficient use of a given privacy budget. We show that, contrary to other forms of DP, natural privacy filters are not free in general. We present a characterization of when a family of private queries admits free natural filters for a given budget. In particular, only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget. Finally, we show that, while the natural approximate-DP filter can fail in the presence of an adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters.

版本更新 · v4arXiv:2504.18489

Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

原文摘要

We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 2$, there exists a hypergraph with $n$ hyperedges such that its $k$-color discrepancy is at least $Ω(\sqrt{n})$. This improves on the previously known lower bound of $Ω(\sqrt{n/\log k})$ due to Caragiannis et al. (arXiv:2502.10516). As an application, we show that our result implies improved lower bounds for group fair division.

cs.DM · cs.GT

版本更新 · v3arXiv:1611.05991

Almost-Polynomial Ratio Almost-ETH-Hardness of Approximating Densest $k$-Subgraph

Pasin Manurangsi

原文摘要

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., 2010), previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer, 2010) and $2^{Ω(\log^{2/3} n)}$ (Alon et al., 2011) respectively. In this work, we propose the Almost-Exponential Time Hypothesis (Almost-ETH), which postulates that no algorithm can solve 3SAT on $n$ variables in $O(2^{n^{1 - γ}})$ time for any constant $γ> 0$. Assuming Almost-ETH, we show that, for any constant $\varepsilon > 0$, there is no polynomial-time algorithm that approximates {\sc D$k$S} to within $2^{(\log n)^{1 - \varepsilon}}$ factor of the optimum. In addition, our result has perfect completeness, meaning that, assuming Almost-ETH, no polynomial-time algorithm can even distinguish between the case in which $G$ contains a $k$-clique and the case in which every induced $k$-subgraph of $G$ has density at most $2^{-(\log n)^{1 - \varepsilon}}$.

cs.CC

新论文 · v1arXiv:2610.34434

Envy-Free Allocations for Random Non-Additive Valuations

Pasin Manurangsi

原文摘要

Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for $n = 2$ agents, they left open whether the same holds for $n > 2$ agents. We resolve this open question in the affirmative: for any fixed number of agents $n$ and any number of items $m$ divisible by $n$, an envy-free allocation exists with probability $1 - o(1)$ as $m \to \infty$. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.

cs.GT · math.CO

版本更新 · v2arXiv:2506.04681Google Research

Urania: Differentially Private Insights into AI Use

Daogao Liu, Edith Cohen, Badih Ghazi, Peter Kairouz, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi 等 11 位作者

原文摘要

We introduce $Urania$, a novel framework for generating insights about LLM chatbot interactions with rigorous differential privacy (DP) guarantees. The framework employs a private clustering mechanism and innovative keyword extraction methods, including frequency-based, TF-IDF-based, and LLM-guided approaches. By leveraging DP tools such as clustering, partition selection, and histogram-based summarization, $Urania$ provides end-to-end privacy protection. Our evaluation assesses lexical and semantic content preservation, pair similarity, and LLM-based metrics, benchmarking against a non-private Clio-inspired pipeline (Tamkin et al., 2024). Moreover, we develop a simple empirical privacy evaluation that demonstrates the enhanced robustness of our DP pipeline. The results show the framework's ability to extract meaningful conversational insights while maintaining stringent user privacy, effectively balancing data utility with privacy preservation.

cs.LG · cs.AI · cs.CL · cs.CR · cs.CY