跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

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

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

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

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

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

浏览论文库

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

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

找到 486 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-09 19:35（北京时间）
新论文 · v1arXiv:2611.03397

Online Algorithms Cannot Find Isolated Perceptron Solutions

Shuangping Li, Gabe Schoenbach

原文摘要

The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density $α> 0$, all but a vanishing fraction of solutions are isolated -- $Ω(n)$-far from all others, in Hamming distance. Such solutions are believed to be algorithmically inaccessible. Nevertheless, efficient algorithms find solutions at some constraint densities $α$. One possible resolution of this apparent contradiction is that the solution space also contains rare well-connected structures, and that algorithms succeed by locating them. Gong, Huang, Li and Sellke (FOCS 2026) proved this for stable algorithms, by showing that such algorithms cannot locate isolated solutions with probability more than $\approx 0.84$. In this work, we study online algorithms, which receive the columns of the constraint matrix one by one and sign each irrevocably upon arrival. This is a widely used class of algorithms in discrepancy minimization, and it includes the algorithm of Jo and Lee (2026), which has one of the best provable guarantees for the binary perceptron. We prove that at any constraint density, any online algorithm outputs an isolated solution with probability $o(1)$. Our proof is based on the observation that the signs an online algorithm has already fixed can be completed to at most one isolated solution, so a successful algorithm must choose the unique correct sign for each of the last few columns. Using the exchangeability of these columns, we show that such an algorithm must match a suffix-parallel baseline, which signs each of them as if it were the next column to arrive. We then use an anti-concentration argument to show that such a baseline rarely produces a unique completion.

cs.CC · cs.DS · math-ph · math.PR

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

Stochastic Matching with Polynomial Degree

Soheil Behnezhad

原文摘要

We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

cs.DS

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

Fast Almost-Uniform Sampling of Random $k$-SAT Solutions

Kun He, Zhidan Li, Kuan Yang

原文摘要

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. Fix a constant $B>0$. For every $k\ge 2^{20}$ and density $0<α\le 2^k/k^{16}$, we prove that, with high probability over a random formula on $n$ variables, every accuracy $n^{-B}\le\varepsilon\le 1/2$ admits a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments with expected running time $$\widetilde O_B\left(\mathrm{poly}(k,α+1)n^{2+η}\right),\quad 0<η\le 2^{16-k}.$$ In particular, the exponent of $n$ is $2+O(2^{-k})$ while the dependence on the width and density is polynomial with a universal degree. This improves the parameter-dependent polynomial exponent of the sampling algorithm of Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) in the density regime $2^k/\mathrm{poly}(k)$. Our algorithm separates a high-degree core from the remaining variables. Every residual formula on the good variables is a deletion subformula of a common bounded-dependency formula. Adapting the rejection--repair framework of Liu, Wang, Yin, Zhang and Zhou (arXiv 2026), we construct an executable sampler for all such residual formulas using ordinary connected violation sets replacing weighted 2-tree witnesses and use it to simulate approximate block heat-bath updates on the core. To analyze the resulting core chain, we integrate out the good variables, represent the core marginal by an absolutely convergent polymer expansion and combine a component-swap variance comparison with an adaptive exploration bound. Absorbing single-component interactions into the local weights leaves interactions of cluster size at least two; retaining their additional decay gives a spectral gap of at least $1/(2s n^{2^{12-k}})$ where $s$ counts core components. Together with the residual sampler, this yields the stated running time.

cs.DS · cs.DM · math.PR

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2609.12352

Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs

Zhidan Li, Kuan Yang

原文摘要

We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant $D$, we establish strong spatial mixing whenever $Dc<1$, where $c$ bounds the Birkhoff contraction coefficients of the interactions. Under the same condition, we also give a deterministic fully polynomial-time approximation scheme (\textbf{FPTAS}) for the partition function. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed $η\in(0,1)$, sufficiently large fixed $d$, and fixed integer $q\ge(2+η)d$, we obtain an \textbf{FPTAS} for counting proper $q$-colorings of $G\sim\mathcal G(n,d/n)$ with high probability over $G$. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).

cs.DS · math.PR

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

Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity

Jiuyao Lu, Georgy Noarov, Aaron Roth

原文摘要

Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family $G$; that is, its residuals should be uncorrelated with every test $g(x)\in G$. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is $\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right)$ when $|G|$ is at least a sufficiently large power of $\log(1/\varepsilon)$. We resolve the sample complexity of $\varepsilon$-calibrated multiaccuracy, showing that it scales as $$ \widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right), $$ separating it from the complexity of multicalibration. The upper bound is obtained by an algorithm that outputs a randomized predictor. For deterministic predictors, we establish the tight rate $$ \widetildeΘ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) $$ whenever $\log|G|=Ω(\log(1/\varepsilon))$. When $\log|G|\le\varepsilon^{-1+κ}$ for any fixed $κ\in(0,1)$, this rate is polynomially larger than the rate for randomized predictors. Thus, unlike for multicalibration, calibrated multiaccuracy exhibits a genuine sample-complexity separation between deterministic and randomized predictors. The matching upper and lower bounds show that the unusual cube-root dependence on $\log|G|$ is intrinsic. At $\log|G|\asymp\varepsilon^{-1}$, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.

cs.LG · cs.DS · math.ST

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

Identification to Subclasses of Chordal Graphs

Petr A. Golovach, Laure Morelle, Daniël Paulusma

原文摘要

An identification of two vertices \(u\) and \(v\) in a graph replaces them with a new vertex that is made adjacent to every vertex of \(N(u)\cup N(v)\setminus \{u,v\}\). We study the \(\mathcal{H}\)-Identification problem, which is to decide whether a given graph \(G\) can be transformed (``identified'') to a graph in \(\mathcal{H}\) by applying at most \(k\) vertex identifications. We determine the classical and parameterized complexity of this problem for various subclasses \(\mathcal{H}\) of chordal graphs, obtaining an almost complete picture for two parameters: \(k\) and \(n-k\). We also consider the Identification problem, which is to test, for two given graphs \(G\) and \(H\), whether \(G\) can be identified to \(H\). We determine the parameterized complexity of this problem when \(H\) is a graph from one of our testbed classes, taking the number of simplicial vertices of \(H\) as the parameter.

cs.DS · cs.CC · math.CO

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

Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

Ran Ben-Basat, William Kuszmaul, Michael Mitzenmacher, Amit Portnoy, Shay Vargaftik

原文摘要

Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any $d$-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within $O(d^{-1/2})$ of a standard Gaussian both in Kolmogorov distance and in $1$-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, while two RHTs suffice for scalar quantization, they may be insufficient for Vector Quantization (VQ), which depends on the joint distribution across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time $O(d)$ check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.

cs.LG · cs.AI · cs.DS · cs.NI

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

Approximating Submodular Orienteering via Rooted Subgraph Decomposition

Lars Rohwedder

原文摘要

The Submodular Orienteering problem asks for an $s$-$t$ walk in a directed graph that maximizes a monotone submodular function over the visited vertices subject to a bound on its length. We give a deterministic polynomial-time approximation algorithm with subpolynomial approximation rate $2^{O(\sqrt{\log n\,\log\log n})}$. This improves over the $O(n^\varepsilon)$ approximation rate that was previously known for every fixed $\varepsilon>0$. We prove a decomposition lemma that partitions a directed graph into rooted subgraphs such that every path intersects only polylogarithmically many such subgraphs. Our algorithm uses this decomposition to construct its recursive subproblems.

cs.DS

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

Optimal Sample Complexity for Max-Cut

Itamar Bender, Robert Krauthgamer

原文摘要

We determine the optimal sample size for constructing value coresets for Max-Cut via uniform vertex sampling. That is, sampling $O(\varepsilon^{-2})$ vertices uniformly at random in $n$-vertex graphs with edge weights in $[0,1]$ yields a reweighted subgraph whose Max-Cut value is an additive $\varepsilon n^2$-approximation to that of the original graph, with constant success probability. This improves the previously known $O(\varepsilon^{-4})$ upper bound and matches the known lower bound. The same guarantee holds also for importance sampling, where vertices are sampled proportionally to their weighted degrees, and we further prove a matching lower bound for this sampling method. Our analysis extends directly to metric Max-Cut, showing that importance sampling of $O(\varepsilon^{-2})$ vertices yields $(1\pm\varepsilon)$-approximation to the Max-Cut value, and to Max-Cut in graphs with edge weights in $[0,1]$ and average weighted degree $\bar d$, achieving the same $(1\pm\varepsilon)$-approximation by either uniform or importance sampling of $O(\varepsilon^{-2}n/\bar d)$ vertices. We additionally show how to use this coreset to recover a cut of expected value at least $OPT-\varepsilon n^2$, by making $O(n\varepsilon^{-2})$ additional edge-weight queries. Finally, our result extends to Max-$r$-Cut, giving an additive $\varepsilon n^2$-approximation using a sample of $O(\varepsilon^{-2}\log(2r))$ vertices.

cs.DS

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

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

Zhidan Li, Kuan Yang

原文摘要

We study the mixing time of the single-site Glauber dynamics for sampling proper $q$-colorings on sparse Erdős-Rényi random graphs $\mathcal{G}(n, d/n)$. We prove that, whenever $q \ge (1 + o_d(1))d$, Glauber dynamics mixes in polynomial time with high probability over $\mathcal{G}(n, d/n)$ for all sufficiently large integers $n$. This improves the previous bound $q = (α^* + o_d(1))d$ where $α^* = 1.7632...$ is the unique solution of $x = \exp(1/x)$ on $[1, \infty)$ by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

math.PR · cs.DM · cs.DS

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

Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing

Rishikesh Gajjala, Arindam Khan

原文摘要

We study weighted edge coloring, where each edge of a graph $G$ has a weight in $(0,1]$, and colors are assigned so that the incident weight of each color at every vertex is at most one. The objective is to minimize the number of colors, denoted by $χ'_w(G)$. This generalizes classical edge coloring (all weights are one) and bin packing ($G$ is a star). Two natural lower bounds are the maximum weighted degree $Δ_w(G)$ and the maximum local bin-packing number $\mathrm{bp}(G)$: the maximum, over vertices, of the minimum number of unit bins needed to pack the incident weights. We have $\lceilΔ_w(G)\rceil\le\mathrm{bp}(G)\leχ'_w(G)$. How closely these local lower bounds approximate the global optimum is a longstanding open problem. Our main result establishes an asymptotic weighted analogue of Vizing's theorem: every simple graph admits a coloring using at most $(1+o(1))\mathrm{bp}(G)$ colors. Thus local bin packings can be made globally consistent with asymptotically vanishing relative loss, even in nonbipartite graphs. Our local-to-global rounding framework coordinates feasible local packing distributions into a partial coloring, leaving only $o(\mathrm{bp}(G))$ uncolored weight at every vertex. For bipartite multigraphs, we prove $χ'_w(G)\le(2+o(1))Δ_w(G)$, establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound $χ'_w(G)\le3\lceilΔ_w(G)\rceil$. Both leading coefficients are optimal, giving weighted analogues of the classical Kőnig--Shannon bounds. Further upper and lower bounds show that the classical factor-$3/2$ separation does not persist with the local bin-packing benchmark. We also disprove the exact weighted-degree conjecture of Feige and Singh [ESA'08]. Our upper bounds have polynomial-time algorithms, and their existence statements are formalized in Lean 4.

math.CO · cs.DM · cs.DS

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

Improved Approximation for Unsplittable Capacitated Vehicle Routing Using Quota Trees

Zhenyu Wang

原文摘要

In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set $V$ of $n$ clients with normalized demands $d_v \in (0,1]$, a depot $r$, a unit vehicle capacity, and symmetric metric travel costs $c$ on $V \cup \{r\}$. We seek a collection of routes of minimum total cost that start and end at $r$, serve each client's entire demand on a single route, and respect the unit capacity constraint $\sum_{v \in V(R)} d_v \le 1$ on every route $R$, where $V(R)$ denotes the clients served by $R$. UCVRP generalizes the metric traveling salesman problem (TSP) and is therefore NP-hard. Capacity constraints add a packing difficulty: when all clients are colocated away from the depot, minimizing the route cost is equivalent to minimizing the number of bins in bin packing. Consequently, UCVRP admits no polynomial-time approximation ratio below $3/2$ unless $\textbf{P=NP}$ (Grandoni, Mathieu, and Zhou, 2023). The classical $3.5$-approximation has been improved; Zhao and Xiao recently obtained a $(2+\ln 2+\varepsilon)$-approximation. In this paper, we give a deterministic polynomial algorithm with approximation ratio $5/2$ for general capacity and arbitrary positive demands. Our algorithm uses local search to select routes through one client with large demand and clients with small demands. It constructs candidate routes using endpoint quota trees after rounding demands and creating vertex copies. We replace selected routes using sets of two to four clients and a squared-weight local search, keeping their client sets disjoint. The remaining clients are served by partitioning a tour constructed using weighted graphic matroid parity. We also give a deterministic polynomial $5/2$-approximation algorithm for the undirected capacitated arc routing problem (CARP) with arbitrary positive edge demands.

cs.DS

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

Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups

Ryosuke Yamano, Tetsuo Shibuya

原文摘要

We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is $O^*(1.3289^n)$, due to Eppstein (SODA 2001). We improve this bound to $O^*(1.3204^n)$ deterministically and $O^*(1.3159^n)$ using randomization. For 4-coloring, the best previously known running-time bound is $O^*(1.7159^n)$, due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to $O^*(1.6975^n)$ deterministically and $O^*(1.6933^n)$ using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time bounds for these two problems that exponentially improve upon the best previously published deterministic bounds. This raises the question of whether randomization offers an inherent exponential advantage for 3- and 4-coloring.

cs.DS

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

Worst-Case to Average-Case Reductions for Basic Linear Algebra

Or Zamir

原文摘要

We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields. A seminal work of Blum, Luby, and Rubinfeld established that any algorithm that successfully multiplies more than $75\%$ of matrix pairs over any finite field, implies an algorithm with essentially the same running time multiplying any pair of matrices. A sequence of follow-ups reduced the needed fraction of successful input pairs to any positive constant. Despite most of the other basic linear algebraic operations being computationally equivalent to matrix multiplication in the worst case, no such worst-case to average-case reductions were known for them. Recently, Vaikuntanathan and Zamir introduced a cryptographic primitive called trapdoor matrices and used them to prove such worst-case to average-case reductions for matrix inversion, solving a linear system, and computing the determinant, all conditioned on common cryptographic assumptions. Our main result is the first unconditional time-preserving worst-case to average-case reduction for matrix inversion. Any algorithm that correctly inverts any constant positive fraction of uniformly random invertible matrices implies a worst-case such algorithm. We also significantly strengthen the conditional reductions based on trapdoored matrices: We establish reductions for deciding invertibility and computing rank at the optimal success thresholds, and qualitatively improve the success threshold needed in the reduction for determinant computation---while previous reductions all required the success probability to be at least $1/2$, we show that any fixed positive average-case success probability suffices for exact worst-case determinant computation over infinitely many finite fields.

cs.DS · cs.CC

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

Revisiting (Bijective) Burrows-Wheeler Transform Space-Time Trade-Off Constructions

Dominik Köppl, Tomohiro I

原文摘要

The bijective Burrows-Wheeler transform (BBWT) replaces the delimiter of the ordinary BWT by a Lyndon factorization and sorts factor conjugates in $ω$-order. It admits quadratic-time constant-workspace algorithms and linear-time linear-space algorithms. We extend the small-space BWT trade-off of Crochemore et al. [JDA,'15] to the BBWT and accelerate both constructions. For $τ\in [3..n]$, let $σ_τ\le\min(σ,τ+1)$ be the maximum construction-batch alphabet size. We construct either transform in $ O\!\left( \frac{n^2}τ \frac{\logτ}{\log\logτ} \right) $ time and $O(τσ_τ)$ additional space, assuming $τσ_τ=O(n)$. This improves the transferred $O((n^2/τ)\logτ)$ bound by a $\log\logτ$ factor. If $σ_τ\in w^{O(1)}$, where $w\inΩ(\log n)$ is the word size, the time improves to $ O\!\left( \frac{n^2}τ + \frac{n\logτ}{\log\logτ} \right). $ For inversion, the same bounds hold with the global alphabet size $σ$ in place of $σ_τ$.

cs.DS

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

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

Yali Aharon-Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma

原文摘要

We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is $exp(Ω(N))$ at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.

quant-ph · cs.CC · cs.DS · math.CO · math.GR

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

A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich

原文摘要

Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in $\widetilde{O}(n m^{2/3}\log W)$ time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of $\widetilde{O}(m\sqrt n \log W)$ in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.

cs.DS · quant-ph

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2610.20079

Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting

Baochun Li, Zongpeng Li, Sirui Liu

原文摘要

In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, we give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is \[ O\!\left(\frac{N}{B}\left[1+ \frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon} \right]\right), \] where $\varepsilon=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $Θ\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.

cs.DS · cs.CC · cs.IT

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2607.18168

A Forward-Backward Weight Analysis of INW for Permutation Branching Programs

Gil Cohen, Dean Doron, Noam Goldgraber

原文摘要

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length \[ O\left((\log w+\log(1/\varepsilon))\cdot \log n\right). \] This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the work of Braverman, Rao, Raz, and Yehudayoff (FOCS 2010; SICOMP 2014), which applies more generally to regular branching programs and already achieves the optimal dependence on $w$, our result improves the dependence on the length $n$, attaining the optimal logarithmic dependence. The generator itself is the classical INW PRG of Impagliazzo, Nisan, and Wigderson (STOC 1994). We show that, for permutation branching programs, the INW generator can be instantiated with expanders whose degrees are polynomial in $w$ and $1/\varepsilon$ and, crucially, independent of $n$. To prove this, we analyze error propagation using program-dependent seminorms tailored to the branching program at hand. These seminorms build on the weight function introduced by Braverman et al. The key point is that, when measured in these adapted seminorms, the error does not accumulate throughout the recursion. Since our analysis relies only on the spectral expansion of the underlying expanders, our seed length tightly matches the recent lower bound for spectral analyses of the INW generator due to Hoza, Pyne, and Vadhan (Algorithmica 2024).

cs.CC · cs.DS

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

Hardness Results for Approximate Distance Labeling in Sparse Graphs

Tsvi Kopelowitz, Ariel Korin, Liam Roditty

原文摘要

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

cs.DS

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

Sketching in Regression: Sketchy in Practice?

Somarddha Das, Soupayan Das Gupta, Koustav Goswami

原文摘要

The Johnson-Lindenstrauss (JL) lemma and its extensions provide tools for solving the $L_2$ regression problem in high-dimensional settings with $n>d$, by transforming a subspace of $\mathbb{R}^{n}$ to a subspace of $\mathbb{R}^{m}$, (where $m<n$) while approximately preserving the norms of elements of the subspace. In this paper, we study the theoretical guarantees made by various JL-based subspace embeddings critically and concretely to gauge their practical applicability. We derive concrete versions of results on subspace embeddings in the literature to establish lower bounds on the reduced dimension as well as to concretely analyze the complexity of the Fast JL, OSNAP Transforms among other embeddings. These analyses suggest that guaranteeing substantial computational savings while maintaining the accuracy of the sketched solution requires data dimensions larger than those typically encountered in practice. We also see that, for practically necessary accuracy requirements or for sparsity requirements for computational gain, existing theoretical guarantees lead to substantially large reduced dimensions. This leads to very stringent data requirements for establishing guarantees of any kind.

cs.DS · math.ST · stat.CO

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

Fine-Grained Complexity Across the Computational Phase Transition

Zhe Ju, Jingcheng Liu, Yitong Yin

原文摘要

How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.

cs.CC · cs.DS · math.PR

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

A characterization of one-sided error testable graph properties in bounded degeneracy graphs

Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl

原文摘要

We consider graph property testing in $p$-degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by sampling uniform neighbors of vertices, and a property is testable with one-sided error if its query complexity is independent of the graph size. It is known that one-sided error testable properties for minor-closed families are exactly those that can be defined by forbidden subgraphs of bounded size. However, the much broader class of $p$-degenerate graphs allows for high-degree ``hubs" that can structurally hide forbidden subgraphs from local exploration. In this work, we provide a complete structural characterization of all properties testable with one-sided error in $p$-degenerate graphs. We show that testability is determined by how copies of the forbidden graphs can share their high-degree vertices: $\mathcal{F}$-freeness is testable if and only if, for every member $H$, every set of roles of $H$ that may be played by high-degree vertices, and every pattern of dependencies between these roles, some member of $\mathcal F$ can be assembled from pieces of copies of $H$ glued according to this pattern. Our results define the exact structural boundary for testability under these constraints, accounting for both the connectivity of individual forbidden subgraphs and the collective behavior of the properties they define.

cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v5arXiv:2507.08846

Precomputed Dominant Resource Fairness

Serdar Metin

原文摘要

Dominant Resource Fairness (DRF) is a resource allocation scheme, addressing the problem of fair allocation of multiple resource types among users with heterogeneous demands for different types of resources. Based on Max-min Fairness, which is a well-established algorithm in the literature for allocating resources in single resource type scenarios, DRF generalises the main principle of maximising the minimum share given to any user to the multiple resource case. It has a number of desirable properties, such as Sharing Incentive, Envy-Freeness, Pareto Efficiency, and Strategy Proofness, that make it preferable over alternatives, and as such, it is widely adopted in distributed systems. In the present study, we revisit the original study and analyse the structure of the algorithm in closer view. The main contribution is an alternative algorithm, which approximates the DRF allocation in linear time, significantly improving over the original algorithm's pseudo-polynomial runtime. We name the new algorithm Precomputed Dominant Resource Fairness (PDRF), after its main working principle. We provide bounds for approximating the original algorithm, and critically evaluate the agreements of aforementioned properties, comparing DRF and PDRF over them. It turns out that there is an adversarial strategy which forces DRF to unfairly allocate more resources to users who submit inflated demands. PDRF, on the other hand, favouring smaller demands, penalises such adversarial behaviour and creates incentive for users to submit their minimal demands.

cs.GT · cs.DC · cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v4arXiv:2503.18974

An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices

Swastik Bhandari

原文摘要

We present FreqBased, a frequency-based algorithm for the maximal square problem in binary matrices. The algorithm maintains a vertical run-length array and a horizontal counter to validate candidate squares, matching the standard single-array dynamic programming algorithm in O(mn) time and O(n) space while reducing the amount of work performed during execution. Experiments on synthetic random binary matrices reveal a clear density-dependent performance transition: FreqBased consistently outperforms the dynamic programming baseline on moderate- and high-density inputs across Intel and AMD processors, achieving peak speedups of 1.175x and 1.277x, respectively, while executing up to 2.08x fewer instructions. On 180 real aerial image masks from the INRIA dataset, FreqBased outperforms the baseline on every instance with speedups of up to 4.63x, confirming that the instruction-count advantage observed on synthetic inputs extends to real binary matrices with spatial structure. Hardware performance counter analysis shows that the performance advantage arises primarily from reduced instruction count despite lower execution efficiency, demonstrating that algorithms with identical asymptotic complexity can exhibit substantially different practical performance depending on input characteristics.

cs.DS · math.OC

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

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM

Dominik Kempa, Tomasz Kociumaka

原文摘要

We study the relative hardness of fundamental problems with state-of-the-art word RAM algorithms that take $O(n\sqrt{\log n})$ time for instances described in $Θ(n)$ machine words ($Θ(n\log n)$ bits). This complexity class, one of six hardness levels identified by Chan and Pătraşcu [SODA 2010], includes problems from several domains: Counting Inversions, string processing problems (BWT Construction, LZ77 Factorization, Longest Common Substring, Batched Longest Previous Factor Queries, Batched Inverse Suffix Array Queries), and computational geometry tasks (Orthogonal Range Counting, Orthogonal Segment Intersection Counting). We offer two main contributions: We establish new links between the above string problems and Dictionary Matching, a classic task solvable using the Aho-Corasick automaton. We restrict Dictionary Matching to instances with $Θ(n)$ binary patterns of length $m = Θ(\log n)$ each, and we prove that, unless these instances can be solved in $o(n\sqrt{\log n})$ time, the aforementioned string problems cannot be solved faster either. Via further reductions, we extend this hardness to Counting Inversions (a fundamental component in geometric algorithms) and thus to Orthogonal Range Counting and Orthogonal Segment Intersection Counting. This hinges on String Nesting, a new problem which is equivalent to Dictionary Matching and can be reduced to Counting Inversions in three steps. Together, our results unveil a single problem, with two equivalent formulations, that underlies the hardness of nearly all major problems currently occupying the $O(n\sqrt{\log n})$ level of hardness. These results drastically funnel further efforts to improve the complexity of near-linear problems. As an auxiliary outcome of our framework, we also prove that several central string problems can be efficiently reduced to their versions over the binary alphabet.

cs.DS

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

Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting

Mengyang Wu, Minghao Wang

原文摘要

We study circuit lower bounds for extended gate bases using exact CNF counting and an extension-ring form of the contraction theorem of OpenAI. The deterministic counting theorem of Claude (Anthropic) yields an $\mathsf{E}^{\mathsf{NP}}$ language requiring $Ω(m\sqrt{\log m}/\log\log m)$ gates over unbounded AND/OR with binary XOR, infinitely often. Using that contraction theorem, a bounded binary base with a linear budget of arbitrary XOR and symmetric gates requires $Ω(m\sqrt{\log m})$ gates infinitely often. These results extend the binary-gate lower bound of OpenAI. Signed long-clause selectors reduce the first counting problem to the difference of two ordinary 3-CNF counts. Affine characters and unit-separated interpolation give the second counting interface, with logarithmic cost per symmetric-gate arity. A quantitative local-reduction transfer accounts for auxiliary variables, branch counts, and integer recovery.

cs.DS · cs.CC

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

Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally

Mengyang Wu, Minghao Wang

原文摘要

Assuming a Boolean tensor contraction hypothesis (Theorem D.1 of OpenAI's recent preprint refuting the Exponential Time Hypothesis), we study exact feedback vertex set counting in general graphs. For an $n$-vertex, $m$-edge simple graph, we compute the complete size distribution deterministically in $\mathrm{poly}(n+m)\,2^{O(n(\log\log n)^2/\sqrt{\log n})}$ time and polynomial working space. The algorithm combines a whole-edge forest identity, subset-index scalar networks, sparse parity filtering, and disjoint high-degree branching. A binomial inversion recovers the multiplicities introduced by exceptional-set guesses. The counting interface supports fixed vertices, minimum solutions, and unranking. Component markers yield induced-tree and induced-path counts within the same bound. Sparse Hamilton, forest, and Steiner edge-tree counting follow from the scalar encoding.

cs.DS

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

Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers

Zachary Friggstad, Pengfei Wu

原文摘要

We study \textsc{Capacitated Facility Location}, a fundamental clustering problem, in the setting of uniform opening costs and non-uniform capacities. We give a polynomial-time $(3+ε)$-approximation for this problem. Our algorithm is a multiple-swap generalization of the local search algorithm by Dabas, Garg, and Gupta (2024), who obtained a $3.732$-approximation. The main technical contribution is the analysis of this natural multiple-swap local-search method: variants of this approach have been analyzed previously, but allowing larger swaps requires new grouping and counting arguments. We also show that a multiple-swap local search algorithm provides a $(3+ε)$-approximation for \textsc{Capacitated Facility Location with Outliers}, again in the same setting of uniform opening costs and non-uniform capacities. This is an improvement over the $6.372$-approximation, again by Dabas, Garg, and Gupta. Finally, we show that the factor $3$ is tight for our local-search framework, and that the same multiple-swap idea does not improve the known locality gap for the non-uniform opening-cost setting.

cs.DS

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

Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy

Ewan Davies, Brian Tan

原文摘要

Local occupancy can be used to bound the expected size of a hard-core independent set. The framework of locally stationary distributions shows that for triangle-free graphs, despite slow mixing at the relevant fugacity parameter, standard Glauber dynamics can be used to find sets close to the local occupancy guarantee. We improve the application of this framework to the hard-core model by replacing a conditional mixing argument with a more direct approach based on a short sequence of single-site updates that, from every initial configuration, achieves the required occupancy inequality. In general graphs, naive conditional mixing estimates or certain problematic structures in the neighborhood can in principle incur running time cost exponential in the maximum degree $Δ$. We design short update sequences that, via our relaxed criterion, yield running times polynomial in $Δ$ for graphs with a hereditary bound $b$ on the density of $K_{t,t}$ subgraphs in neighborhoods. Our methods handle the case where $t$ and $b$ can grow with the maximum degree, and the resulting algorithm attains the random graph shattering threshold when they grow sufficiently slowly. That is, we give improved local occupancy parameters and a short update sequence analysis which together show that Glauber dynamics finds independent sets of size $(1-o(1))n(\logΔ)/Δ$ in time polynomial in $n$ and $Δ$ whenever $t$ and $b$ are constant or grow suitably slowly. In a similar regime, we also establish that the (correspondence) chromatic number is at most $(1+o(1))Δ/\logΔ$ which improves upon prior results by a factor of at least $4$ in the case $t\ge 4$.

cs.DS · math.CO

查看论文
arXiv ↗PDF ↗