跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文，不再错过。

覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。

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

全站更新概况

+1072新增论文
+845其中 AI 相关
+94已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-10 07:06 · 全站最近入库：2026-11-09 13:22各信源进度 →

统计口径与数据新鲜度

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

最近完成检查：2026-11-10 07:06最近发现新增版本：2026-11-09 13:22库内论文最新更新时间：2026-11-07 02:59

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

18,172 已收录论文15,506 AI 相关4,527 有修订112 HF 社区发现

浏览论文库

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

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

找到 9 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-10 07:04（北京时间）
新论文 · v1arXiv:2611.09656

From Function Inversion to Preimage Reporting

Mathieu Vannimmen

原文摘要

Given an arbitrary function $f:[N]\to[M]$, the function inversion problem asks to preprocess $f$ and to be able to, when given some $y\in [M]$, decide whether there exists some $x\in [N]$ such that $f(x)=y$ and if so, to report such an $x$. Recently, Fiat-Naor's solution to this problem has seen significant traction in theoretical computer science, and allowed for several conjectures related to meta-complexity and the 3SUM problem to be broken. In this paper, we consider the natural extension of the function inversion problem that we call preimage reporting. Here, instead of having to report only one $x\in [N]$ such that $f(x)=y$, the whole set $f^{-1}(y)$ must be found. We present a new general method to convert any arbitrary function inversion scheme into an efficient corresponding preimage reporting scheme. In particular, if $Δ$ is the maximal indegree of $f$, we show that we can perform preimage reporting using space $S$ in time $T$ for any $T$ and $S$ satisfying $TS^2=N^2 Δ$, matching a variant of a tradeoff obtained by Fiat and Naor for function inversion. This last result implies an improvement over the corresponding function inversion scheme itself, which constitutes the first function inversion scheme whose query time is inversely proportional to $|f^{-1}(y)|$. We derive new simple solutions for the $k$SUM-indexing with reporting and Jumbled indexing with reporting problems.

cs.DS

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

Tight Bounds for Paging with Delay and Joint Replenishment with Varying Opening Costs

Joseph, Naor, Tomer Tsachor

原文摘要

We study weighted paging with delay, a generalization of classical paging in which requests may be served after their arrival, incurring delay costs while awaiting service. This model allows the algorithm to delay service and batch service requests over time, but also introduces significant challenges due to overlapping requests. While the problem is well understood in the unweighted setting, where optimal $O(\log k)$-competitive algorithms are known, the weighted case remains more elusive. The best previously known randomized algorithm, due to Gupta, Kumar, and Panigrahi, achieves an $O(\log k \log n)$-competitive ratio, leaving a gap between weighted and unweighted settings. We obtain a randomized $O(\log k)$-competitive algorithm, matching the lower bound inherited from classical paging. The core of our approach is a structural decomposition that separates the evolution of the cache over time from scheduling additional page loads, so as to make the solution feasible. We develop this approach first for paging with time windows, the special case in which each request must be served within a specified time interval. Given a sequence of cache configurations, we reduce the problem of augmenting this sequence to a feasible solution to a variant of the Joint Replenishment Problem with deadlines (JRP-D) with time-dependent opening costs. We design a constant-competitive online algorithm for this variant under a prediction model whose required information is available online in our paging reduction. Combining this algorithm with an existing online construction of cache configurations yields an $O(\log k)$-competitive algorithm for paging with time windows. We then extend the framework to obtain the same guarantee for weighted paging with a general delay function.

cs.DS

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

Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting Set

Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, Michael Zlatin

原文摘要

We study the Online Connectivity Augmentation Problem (OCAP) with cut arrivals. In this problem, we are given a $k$-edge-connected graph $G = (V,E)$ with $|V| = n$ and a set of links $L \subseteq \binom{V}{2}$. In each iteration, a minimum cut arrives to be augmented, and we seek to maintain a smallest set of links crossing all such cuts. This problem is a special case of online hitting set in which the ground set is $L$ and a sequence of sets to be hit arrive from $\mathcal{C} = \{δ_L(C) : |δ_E(C)| = k\}$. As such, OCAP admits a $O(\log^2 n)$-competitive algorithm using the classical algorithm for Online Set Cover of Alon, Awerbuch, Azar, Buchbinder, and Naor. If $k$ is odd, then OCAP reduces to the case where $G$ is a tree. This case was studied by Naor, Umboh, and Williamson, who gave an optimal $O(\log n)$-competitive algorithm, which even holds in weighted setting. Recently, Garg and Subramanian gave an $O(\log n)$-competitive algorithm for unweighted OCAP which holds in the popular node-arrival model, but not for cut-arrivals. No better than $O(\log^2 n)$-competitive algorithm is known for weighted OCAP. In this paper, we provide a nearly optimal $O(\log n \log \log n)$-competitive algorithm for weighted OCAP under cut-arrivals and an optimal $O(\log n)$-competitive algorithm for unweighted OCAP with cut-arrivals. We also give an $O(1)$ algorithm for Online Cycle Augmentation under node-arrivals. Since no $o(\log n)$-competitive algorithm is possible on a cycle with cut-arrivals, this establishes a separation between the best competitive ratio achievable in the two arrival models.

cs.DS

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

Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation

Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, Louis-Charles Thibodeau

原文摘要

In this paper, we show for the first time that post-quantum one-way permutations are sufficient for perfect zero-knowledge classical arguments for all of NP with security guaranteed against quantum adversaries. We first establish that Naor, Ostrovsky, Venkatesan, and Yung's bit commitment scheme built from any permutation using interactive hashing, called the NOVY scheme, is sum-binding and collapse-binding against quantum polynomial-time committers provided the permutation is post-quantum one-way. We then show that the collapse-binding property of the NOVY scheme allows for Blum's perfect zero-knowledge argument for HAMCYCLE to remain so exactly as it stands against quantum adversaries.

quant-ph · cs.CR

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

An Integrality-Gap Lower Bound of 1.2325 for Minimum Multiway Cut

Dimitar Chakarov, Yury Makarychev

原文摘要

We prove that the integrality gap of the Călinescu-Karloff-Rabani relaxation for Minimum Multiway Cut is at least $1.2325$ when the number of terminals is large. By a result of Manokaran, Naor, Raghavendra, and Schwartz (2008), it is therefore NP-hard, under the Unique Games Conjecture, to approximate Minimum Multiway Cut within a factor of $1.2325$. This improves the previously best known lower bound of $1.20016$ due to Bérczi, Chandrasekaran, Király, and Madan (2020).

cs.DS

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

Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

原文摘要

The Multiway Cut problem is among the most well-studied problems in the area of combinatorial approximation algorithms. The currently best approximation ratio for the problem is 1.2787, obtained recently by the authors (2026). The best lower bound on the approximation ratio that can be achieved for the problem in polynomial time, under the Unique Games Conjecture (UGC), is 1.20016, obtained by Bérczi, Chandrasekaran, Király, and Madan (2020), building on and slightly improving a bound of $\frac65=1.2$, obtained by Angelidakis, Makarychev, and Manurangsi (2017) by introducing the important framework of non-opposite multiway cuts. We obtain a substantially improved lower bound of 1.22232 on the approximation ratio of the Multiway Cut problem. Manokaran, Naor, Raghavendra, and Schwartz (2008) showed that under UGC, the approximation ratio of Multiway Cut is equal to the integrality ratio of a simple LP relaxation, known as the CKR relaxation, introduced by Călinescu, Karloff, and Rabani (2000). Thus, stronger LP relaxations are not required for obtaining an optimal approximation algorithm for the problem. We show, however, that relying on the framework of Angelidakis, Makarychev, and Manurangsi (2017), stronger LP relaxations from the Sherali-Adams hierarchy for non-opposite multiway cuts can be used to obtain improved integrality ratios for the CKR relaxation, and hence improved lower bounds on the approximation ratio of the Multiway Cut problem. One of the novel features of our analysis is considering a continuous limit of discrete LPs defined on a simplex. Our proof of the new 1.22232 bound is completely analytic. We also present strong numerical evidence that suggests that our techniques can be used to improve the lower bound to at least 1.23003.

cs.DS · cs.CC

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

Optimal Zonotope Containment via Adaptive Gaussian Sampling

Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo, Ruben Skorupinski

原文摘要

We investigate the convex-body containment problem $\max\{s >0 : s Z \subseteq Q\}$, where the outer body $Q \subseteq \mathbb{R}^d$ is described by a membership oracle and the inner body $Z \subseteq \mathbb{R}^d$ is a zonotope. Our main result is a sampling-based $O(\sqrt{d/\log d})$-approximation algorithm for this problem that matches the lower bound of $Ω(\sqrt{d/\log d})$ by Khot and Naor in the oracle model. Starting from approximate Lewis position, the algorithm samples Gaussian directions and adaptively shortens and repositions the generators. Its analysis combines preservation of the support in a fixed direction with contraction of the corresponding functional after renormalization. Crucially, the algorithm works directly with the input generators and does not use zonotope sparsification. We complement this result with a \emph{universal} $Ω(\sqrt{d/\log d})$ lower bound holding for \emph{all} full-dimensional zonotopes when the number of oracle queries is polynomial in $d$. Finally, we consider containment problems $\max\{s >0 : s K \subseteq Q\}$, for general convex bodies $K \subseteq \mathbb{R}^d$. A result of Nasz{ó}di on approximating $K \subseteq \mathbb{R}^d$ by a polytope implies a $Θ(d/\log d)$ approximation algorithm in polynomial time when the centroid of $K$ is the origin. We show the tightness of this approximation factor in the oracle model via a reduction to the circumradius computation. Our lower bound holds for centrally symmetric convex sets, implying that Barvinok's optimal $O(\sqrt{d})$-approximation of a centrally symmetric convex body by a polytope with a polynomial number of vertices cannot be computed in polynomial time.

cs.DS · math.MG

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

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)

Youlong Ding, Aayush Jain, Ilan Komargodski

原文摘要

We obtain new $\mathsf{NC}^1$-computable pseudorandom functions (PRFs) from various standard assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2) from the \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025], [Ding-Jain-Komargodski, TCC 2026]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS '97, J. ACM '04]. Technically, our results follow from a new generic transformation that converts weak PRFs computable in depth $d(n) = Ω(\log n)$ to (strong) PRFs computable in depth $O(d(n))$. Roughly speaking, our approach combines \emph{tapering} the internal state of the classical GGM tree (so that the per-leveldepth decreases geometrically) with a two-stage security proof that transitions from a computational to an information-theoretic argument.

cs.CC

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

A Sharp Dynamic Haussler Lemma

Shihao Shao, Dacheng Tao

原文摘要

Haussler's covering lemma (JCTA 1995) gives the sharp $(C/δ)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\varepsilon<1/4$, a matching worst-case lower bound $(c/\varepsilon)^{pd}$ holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of $p$. For $p=2$, this resolves the horizon-independent sequential $\ell_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C/δ)^{\operatorname{Ldim}(\mathcal H)}$ global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.

cs.LG · cs.DS

查看论文
arXiv ↗PDF ↗