跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

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

找到 10 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
版本更新 · v2arXiv:2611.06717

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

Piaoyang Cui, Yiming Liu, David P. Woodruff

原文摘要

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

cs.DS

新论文 · v1arXiv:2611.12867

SparseStack 的最优单侧注入性

Optimal Injectivity of the SparseStack

Lorenzo Beretta, Simone Bombari, Margalit Glasgow, Raphael Arkady Meyer, Kijun Shin, David P. Woodruff

AI 速读 基于摘要

作者证明 SparseStack 草图在行稀疏度约 √log r 时即可实现线性维度的单侧子空间注入,并给出匹配下界,说明该尺度是本质的。

cs.DS

查看原文摘要

An Oblivious Subspace Injection (OSI) is a random sketching matrix that reliably preserves the minimum singular value of any fixed subspace with high constant probability, requiring only a one-sided spectral lower bound without controlling upper singular values. While classical Oblivious Subspace Embeddings (OSEs) fundamentally require row sparsity $Ω(\log r)$ at linear sketch dimension $k = O(r)$, we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to $\log\log r$ factors) upper and lower bounds of $\tildeΘ(\sqrt{\log r})$. First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension $k = Θ(r)$ with row sparsity only $ζ= O(\sqrt{\log r})$, well below the $Θ(\log r)$ barrier where standard operator-norm concentration fails. Second, we establish a matching lower bound: any isotropic random sketching matrix satisfying a mild row-overlap condition requires row sparsity $ζ= Ω(\sqrt{\log r / \log \log r})$ to achieve linear-dimension injectivity, confirming that the $\sqrt{\log r}$ scale is fundamental. To bypass the lack of an operator-norm upper bound when $ζ= O(\sqrt{\log r})$, we decouple the sketch into two independent halves and introduce three techniques: (i) a uniform lower bound for flat vectors via randomized rounding, controlling discretization error using solely the Frobenius norm; (ii) a Gaussian truncation and minimax duality argument showing that all non-flat vectors escaping injectivity in the first half concentrate on a single universal coordinate subset $I \subseteq [n]$ of size $O(r/ζ)$, bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to $e^{-Ω(ζ^2)} \ll 1/r$, reliably preserving these heavy coordinates.

新论文 · v1arXiv:2611.11151

Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL

Ying Feng, David P. Woodruff

原文摘要

For two $d$-dimensional point sets $A, B$ of size $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b)$, where $\mathsf{dist}$ is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the $\ell_p$ norm for $1 < p \le 2$. For the general case $1 < p < 2$, we utilize lopsided $\ell_p$ to $\ell_1$ embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to $O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2)$ total time. For the specific Euclidean case ($p=2$), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous $\ell_1$-specific Chamfer algorithm in $\ell_2$. These achieve a runtime matching the recent state-of-the-art $\ell_1$ result of $O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2)$, improving upon the previous $O(nd \log n/\varepsilon^2)$ bound for $\ell_2$. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.

cs.DS · cs.LG

版本更新 · v2arXiv:2509.16801

Sublinear Time Quantum Sensitivity Sampling

Zhao Song, David P. Woodruff, Lichen Zhang

原文摘要

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume $n,d\geq\mathrm{poly}(k/ε)$ and, for regression, $n\geq\mathrm{poly}(d)$: - $k$-median/$k$-means: For $n$ points in $\mathbb{R}^d$, we build an $ε$-coreset of input points of size $\tilde O(k^{4/3}ε^{-2})$ (resp. $\tilde O(k^{3/2}ε^{-2})$) in time $\tilde O(ε^{-1}n^{0.5}dk^{1.67})$ (resp. $\tilde O(ε^{-1}n^{0.5}dk^{1.75})$). Our better $d$- and linear $1/ε$-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for $d\geqΩ(k^{7/3})$ (resp. $Ω(k^{2.5})$). - $\ell_p$ regression: For $\min_x\|Ax-b\|_p$, $A\in\mathbb{R}^{n\times d}$, we build an $ε$-coreset of size $\tilde O_p(d^{\max\{1,p/2\}}ε^{-2})$ in time $\tilde O_p(n^{0.5}d^{1.5}ε^{-1})$ for $p\leq 2$ and $\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5}))$ for $p>2$, matching [Liu and Ji, ICML'26] for $p\leq 2$ and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all $p>2$. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-$k$ approximation of $A\in\mathbb{R}^{d\times n}$ free of data-dependent parameters, running in $\tilde O(n^{0.5}dk^{0.5}ε^{-0.5})$ time with factored output (plus $\tilde O(nk^2ε^{-2})$ to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity $S$, any quantum algorithm outputting an $ε$-coreset of size $o(\sqrt{nS})$ needs $Ω(\sqrt{nS})$ queries, so our query complexity is optimal up to $\mathrm{poly}(ε^{-1},\log n)$ and VC-dimension factors.

cs.DS · cs.LG · quant-ph

新论文 · v1arXiv:2611.09809

超越 n/2 阈值:计算汉明重量与对称函数的量子查询复杂度

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff

AI 速读 基于摘要

作者构造了一类需要 n/2+Ω(n^{1/3}) 次量子查询的对称布尔函数,并给出用 n/2+O(n^{1/3}) 次查询精确恢复汉明重量的算法,从而确定该加性阶数的最优性。

quant-ph · cs.CC

查看原文摘要

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

新论文 · v1arXiv:2611.08699

Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams

Elena Gribelyuk, Honghao Lin, Xin Lyu, Mahbod Majid, David P. Woodruff, Huacheng Yu, Samson Zhou

原文摘要

Classical streaming algorithms and statistical mechanisms frequently fail when future inputs or queries depend adaptively on prior outputs. In this work, we resolve central open questions in both adaptive data analysis (ADA) and adversarially robust turnstile streaming by introducing a unified hierarchical estimator-corrector-learner framework. For adaptive data analysis over an unrestricted domain, we design a randomized mechanism that answers $k$ adaptively chosen statistical queries to within additive error $α$ using $\tilde{O}(\frac{\sqrt{k}}α + \frac{1}{α^2})$ samples, nearly matching the lower bounds of Hardt and Ullman [FOCS 2014] and Steinke and Ullman [COLT 2015] while improving upon the classic $\tilde{O}(\frac{\sqrt{k}}{α^2})$ bound of Dwork et al. [STOC 2015] and Bassily et al. [STOC 2016]. For known finite domains $U$, we combine our mechanism with private multiplicative weights to improve the sample complexity to $\tilde{O}\left(\frac{1}{α^2}+ \min\left(\frac{\sqrt{k}}α, \frac{\sqrt{\log |U|}}{α^2}\right)\right)$. Building on our ADA mechanism, we construct a fixed linear sketch with a stateful decoder that answers $\tilde{O}(\frac{1}{ε^2})$ adaptive $F_2$ moment estimation queries to within a $(1\pmε)$-multiplicative factor using $\tilde{O}(\frac{1}{ε^2})$ bits of space. Finally, by embedding this sketch into a binary-tree recursion, we obtain the first nearly space-optimal adversarially robust algorithm for $F_2$ estimation on insertion-deletion streams. Our algorithm uses $\tilde O(\frac{1}{ε^2})$ bits of space, improving upon the $\tilde{O}(\frac{1}{ε^4})$ bound of Gribelyuk et al. [STOC 2026] and matching the insertion-only bound of Woodruff and Zhou [FOCS 2021]. This demonstrates that no asymptotic space overhead in $ε$ is required to achieve adversarial robustness in the turnstile model.

cs.DS

新论文 · v1arXiv:2611.07678

Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering

Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer, David P. Woodruff, Shenghao Xie, Samson Zhou

原文摘要

We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$-approximate $k$-Median and $k$-Means in Euclidean space $\mathbb{R}^d$, using $\tilde{O}(kd \mathrm{poly}(ε^{-1}))$ space. This result significantly improves a recent $O(d\log n)$-approximation for $k$-Median [Gribelyuk, Lin, Woodruff, Yu, and Zhou, FOCS 2026], and is furthermore the first algorithm whose space is linear in $kd$, even in the oblivious (non-adaptive) setting. We develop several new techniques which may be of independent interest, including a new data-oblivious Euclidean primitive called hierarchical Lipschitz assignment, a robust dimensionality reduction for clustering, and a robust streaming algorithm for inner-product queries.

cs.DS

新论文 · v1arXiv:2611.03604

Near-Optimal Space and Time Cut Sparsification in Turnstile Streams

Honghao Lin, Vahab Mirrokni, David P. Woodruff

原文摘要

A seminal result of Ahn, Guha, and McGregor (PODS'12) showed that a cut sparsifier of an unweighted graph can be computed from a near-linear number of linear measurements. Later work extended this to spectral sparsifiers (Kapralov et al., FOCS'14) and to near-linear recovery time (Kapralov et al., SODA'20). For weighted graphs, these sketches rely on grouping edges by weight, which general turnstile streams do not allow. Chen, Khanna, and Li (FOCS'22) removed this limitation, using $\tilde{O}(n/\varepsilon^3)$ bits of space. We improve the space to $\tilde{O}(n/\varepsilon^2)$ bits. Our algorithm makes one pass over a general turnstile stream of a weighted graph, processes each update in $\tilde{O}(1)$ time, and recovers, in $\tilde{O}(n/\varepsilon^2)$ time, a reweighted subgraph with $O(n\varepsilon^{-2}\log^2 n)$ edges that preserves every cut within a factor of $1\pm\varepsilon$. Its space, update time, and recovery time are all optimal up to polylogarithmic factors.

cs.DS

新论文 · v1arXiv:2610.38860

Fast Perfect $L_2$ Sampling

David P. Woodruff, Samson Zhou

原文摘要

Perfect $L_2$ sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency, with applications to dynamic join size estimation, query optimization, heavy-hitters, sampling from self-joins, and real-time monitoring of evolving datasets. The setting $p=2$ is also the largest $p$ for which $L_p$ sampling can be achieved in polylogarithmic space. However, existing space-optimal perfect samplers rely on explicit polynomial duplication, requiring inefficient polynomial update times per stream arrival. Resolving a open question left by Swartworth, Woodruff, and Zhou [FOCS 2025], we present a perfect $L_2$ sampler that achieves an expected $\text{polylog}(n)$ update time while maintaining an optimal $\tilde{\mathcal{O}}(\log^3 n)$ bits of space.

cs.DS

版本更新 · v3arXiv:2602.03837Google DeepMindGoogle Research

Accelerating Scientific Research with Gemini: Case Studies and Common Techniques

David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Branzei, Michael P. Brenner 等 36 位作者

原文摘要

Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks, their ability to contribute to novel, expert-level mathematical discovery is less understood. We present a collection of case studies demonstrating how researchers have successfully collaborated with advanced AI models, specifically Google's Gemini-based models (in particular Gemini Deep Think and its advanced variants), to solve open problems, refute conjectures, and generate new proofs across diverse areas in theoretical computer science, as well as other areas such as economics, optimization, and physics. Based on these experiences, we extract common techniques for effective human-AI collaboration in theoretical research, such as iterative refinement, problem decomposition, and cross-disciplinary knowledge transfer. While the majority of our results stem from this interactive, conversational methodology, we also highlight specific instances that push beyond standard chat interfaces. These include deploying the model as a rigorous adversarial reviewer to detect subtle flaws in existing proofs, and embedding it within a "neuro-symbolic" loop that autonomously writes and executes code to verify complex derivations. Together, these examples highlight the potential of AI not just as a tool for automation, but as a versatile, genuine partner in the creative process of scientific discovery.

cs.CL · cs.AI