跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

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

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

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

全站更新概况

+788新增论文
+627其中 AI 相关
+81已有论文修订
+100新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查：2026-11-09 11:20最近发现新增版本：2026-11-09 11:19库内论文最新更新时间：2026-11-06 21:58

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

17,888 已收录论文15,288 AI 相关4,419 有修订112 HF 社区发现

浏览论文库

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

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

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

Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

Alexandru Popa

原文摘要

The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

cs.CC · cs.DS

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

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

L. Sunil Chandran, Rishikesh Gajjala

原文摘要

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

cs.DS · cs.CC · cs.CG · cs.IT

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

A Fixed-Parameter Algorithm for 4-Block Integer Programming

Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz

原文摘要

We give a fixed-parameter tractable (FPT) algorithm with running time $f(k,\barΔ)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute entry $\barΔ$ in the local-column blocks. This result resolves a long-standing open question in parameterized complexity, and answers a conjecture by Eisenbrand and Rothvoss (2026) in the positive. This result has several implications for other block-structured integer programming models, including mixed fracture number and special cases of 4-block programs with large entries outside of the diagonal. Important tools for this algorithm are structural properties of generalized $n$-fold integer programs shown by Ligthart~(2026) and an algorithm by Veselov, Gribanov, Zolotykh and Chirkov~(2020) for optimizing discrete convic functions. Independently and shortly after the first version of our paper appeared, Koutecký, Lassota, and Ligthart (2026) obtained an FPT algorithm for 4-block integer programming.

cs.CC · cs.DS

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

Improved Algorithms for Unrelated Crowd Worker Scheduling in Mobile Social Networks

Chi-Yeh Chen

原文摘要

This paper studies task scheduling with unrelated crowd workers in mobile social networks, where the service time of a task depends on the crowd worker that performs it, and the objective is to minimize the total weighted completion time. For identical crowd workers, we tighten the approximation ratio of the Largest-Ratio-First (LRF) algorithm and update the competitive ratio of its online version. For unrelated crowd workers, we show that the time-indexed rounding framework of Im and Li remains valid when worker-dependent contact delays are added, which yields a randomized algorithm with an expected approximation ratio of 1.45; this improves upon the expected ratio of $1.5+ε$ obtained in our previous work for identical crowd workers. We also derandomize this algorithm. To improve computational efficiency, we further propose an algorithm that exploits the optimality of the Smith-ratio order on a single crowd worker, and we prove that it is a deterministic 1.5-approximation algorithm and that its polynomial-time version achieves an approximation ratio arbitrarily close to 1.5. Experiments on synthetic instances and on instances derived from real contact traces show that this algorithm outperforms three variants of LRF in all tested settings, with the largest advantage when the crowd workers are highly heterogeneous, performs on par with a local-search heuristic for unrelated machines, and is within 0.4\% of the optimum on average on small instances that can be solved exactly.

cs.DS

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

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

Ziyi Cai, Shuangping Li, Yiheng Shen, Kangning Wang, Peng Zhang

原文摘要

Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.

cs.DS · cs.AI · cs.CL · cs.DM · cs.LG

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

Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints

Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang

原文摘要

We characterize the optimal space for one-pass spanning-forest computation in dynamic streams of $v$-vertex simple graphs with failure probability at most $δ$. Nelson and Yu proved an $Ω(v\log^2v\log(v/δ))$-bit lower bound, establishing the AGM algorithm's optimality for each fixed $0<ε<1$ and $2^{-v^{1-ε}}<δ\le1/4$. We resolve the remaining high-confidence regime: for every $0<δ\le1/4$, matching lower bounds and an algorithm give \[ Θ\!\left(\min\left\{v^2,\;v\log(v/δ)\log^2\!\left(2+\frac{v}{\log(v/δ)}\right)\right\}\right) \] bits, improving space by up to a factor of $Θ((\log v/\log\log v)^2)$ in this regime. We also study streams with at most $Z$ previously inserted edges deleted and not yet reinserted at report time, where the integer $Z\ge0$ is given in advance. Total deletions, restorations, and intermediate absence counts are unrestricted. For a single report and every $0<δ\le1/4$, matching lower bounds and a one-pass randomized algorithm yield optimal space $Θ(\mathcal L(v,Z,\log(1/δ)))$ bits, where $x_Z(t)=\min\{Z+1,v,\sqrt{vt}\}$ and \[ \mathcal L(v,Z,t)=v\log v\min\{\log^2v,\log^2(Z+2)\} +vt\log\!\left(1+\frac{x_Z(t)}t\right)\log\!\left(1+\frac v{x_Z(t)}\right). \] At zero error, a lower bound for all zero-error algorithms and a matching deterministic algorithm give optimal space \[ Θ\!\left(\min\{v^2,v(Z+1)\log(1+v/(Z+1))\}\right) \] bits. Together, these results characterize the memory required across all confidence levels and report-time edge-loss bounds.

cs.DS · cs.CC

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

An FPRAS for Counting Common Bases of Two Matroids

Xiaoyu Chen, Kuikui Liu

原文摘要

We design the first fully polynomial-time randomized approximation scheme ($\mathsf{FPRAS}$) for approximately counting and uniformly sampling common bases of two matroids given by their independence oracles. Moreover, our algorithms generalize far beyond this to Hadamard products of two probability measures on the Boolean cube satisfying a simple nonnegative curvature condition. These algorithmic primitives have myriad applications in statistical physics, polyhedral combinatorics, the theory of quantum many-body systems, and beyond. The central difficulty is that the hard constraints imposed by the two input matroids (or the two input measures, more generally) obstruct traditional approaches based on local Markov chains. Relaxing these constraints can restore rapid mixing, but configurations that satisfy the original hard constraints may become exponentially rare if this is done naïvely. Our main contribution is a novel approach for approximate counting that marries Markov chain Monte Carlo (MCMC) with convex programming to overcome these obstacles: - We relax the intersection by imposing an overlap penalty on the product measure formed by the two input measures. We prove, via an integrated Bochner-type method, that this "soft intersection" satisfies a Poincaré Inequality uniformly over all external fields. - We use samples from the relaxed distribution to solve a dual maximum entropy convex program inspired by the Gurvits capacity. This program reweights the soft intersection measure using external fields to boost the aggregate probability of configurations satisfying the hard intersection constraint, without changing their relative weights. We bound the success probability directly using the uniform Poincaré Inequality and smallness of the gradient norm. AI Disclosure: GPT-5.6 Sol Ultra and GPT-6 Astra Ultra were heavily used to develop the ideas in this paper.

cs.DS · cs.CC · cs.DM · math.PR

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

XOR-Functions and Beyond in the Random Query Model

Sumegha Garg, Janani Sundaresan, Santhoshini Velusamy

原文摘要

We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model. On input $x$, a branching program receives independent samples $(i,x(i))$, where $i$ is uniform in $[n]$. We want to evaluate $f(x)$ while minimizing the width $2^S$ and the length $T$ of the branching program. There is a simple upper bound of $T = \tilde{O}(n)$, $S = O(n)$: coupon-collector shows that $\tilde{O}(n)$ samples suffice, and they can be stored in $O(n)$ space. Raz and Zhan (ITCS 2020) introduced this model and studied the zero-error setting. In the bounded-error setting, Dinur (SODA 2024) proved $TS = \tildeΩ(n \cdot inf[f])$, where $inf[f]$ is the total influence of $f$. For many functions with low influence such as Equality and Tribes, this lower bound can leave a substantial gap from the best known upper bounds. Our main result is a stronger lower bound of $T(S+\log T) = Ω(n \cdot sens[g])$ for any XOR-function $g(x,y)= f(x \oplus y)$, where $sens[g]$ is the sensitivity of $g$. Through simple corollaries, we get tight nearly-quadratic time--space lower bounds for Tribes and Equality, despite their low influence. Our proof introduces a new notion of information complexity tailored to the random query model along with a corresponding direct-sum argument which may be of independent interest. Dinur also proved a tight bound of $TS = Ω(n^2)$ for Majority, whose influence is only $Θ(\sqrt{n})$, and asked whether an alternative characterization of Boolean functions could give a unified proof of tight results for a broader class of functions, including Majority. We answer this open question by proving $TS = \tildeΩ(n \cdot dgn[f])$, where $dgn[f]$ is the degeneracy of the sensitivity graph of $f$ (for Majority, this is $Θ(n)$). We also prove that this bound is tight for all symmetric functions up to logarithmic factors.

cs.DS

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

Fast mixing of the SYK model at high temperatures

Yiyi Cai, Yongtao Zhan, Alexander Zlokapa

原文摘要

The Sachdev-Ye-Kitaev (SYK) model is a strongly interacting fermionic system. Its dynamics are difficult to analyze with Lieb-Robinson bounds and cluster expansions due to its all-to-all disordered interactions. We prove that, with high probability over the disorder, the SYK model admits a quantum Gibbs sampler with a system-size-independent spectral gap at sufficiently high constant temperatures. This yields polynomial-time preparation of SYK Gibbs states on a quantum computer. While prior non-rigorous computations that suggested SYK thermalization were limited to studying local correlators, we emphasize that our result holds up to arbitrary inverse polynomial trace distance. Our proof introduces the pseudo-Lindbladian approach to fermions then applies two key new ideas: a Bochner inequality for quantum dynamics, and an especially simple SYK analysis based on a comparison to classical dynamics.

quant-ph · cond-mat.dis-nn · cs.DS · math-ph

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

Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

Yiming Gao, Xuyuan Han, Honggang Hu

原文摘要

We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $α>1$, shifted DGS on arbitrary lattices at width $σ\geαη_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3η_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.

cs.DS · cs.CR

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

A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five

Xiaoyu Chen, Kuikui Liu

原文摘要

It is proved that, for every $δ\in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+δ)Δ$ and the underlying graph has girth at least $5$ and maximum degree $Δ= Ω_δ(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+δ)(1-β)Δ$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.

cs.DS · cs.DM · math.PR

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

State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron

Jianan Zhang, Shuangping Li

原文摘要

The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou (STOC 2025) analyzed one linear program followed by iterative rounding. In this work, we overcome this limitation and give a precise analysis of iterated linear programming for the binary perceptron. (1) For Gaussian matrices and any fixed number of rounds, we characterize the iterated linear programs exactly through a deterministic state-evolution recursion. (2) Adding a final rounding step, we obtain a randomized polynomial-time algorithm for the binary perceptron. Numerical evaluations of the recursion provide evidence that it succeeds at constraint density $α=0.60$ with zero margin, well beyond the range $α\le0.1$ guaranteed by the single-LP analysis and $α\approx0.327$ (Jo and Lee, 2026), the best guarantee so far. (3) We establish universality, showing that the same characterization holds for matrices with i.i.d. entries drawn from any centered, unit-variance subgaussian law. The key idea of our proof is that, although conditioning on earlier rounds makes the matrix non-Gaussian, its conditional law can be computed explicitly and remains close to a Gaussian law, so the convex Gaussian min-max theorem applies in every round. For universality, we compare Gaussian and subgaussian matrices through the Lindeberg principle, using a regularized version of each linear program.

cs.DS · cs.CC · math.PR

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

Metric TSP in Sublinear Time: Breaking Two Approximation

Amir Azarmehr, Soheil Behnezhad

原文摘要

The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can break the 2-approximation barrier has remained a major open problem. See problem 71 on sublinear.info. This paper resolves this open problem. We show there are fixed $\varepsilon, δ> 0$ such that a $(2-δ)$-approximation of metric TSP value can be obtained with $O(n^{2-\varepsilon})$ queries. Here $n$ is the number of vertices, and the input size is $Θ(n^2)$.

cs.DS

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

Testing Implies Distance Estimation with Polynomial Loss

Gaia Carenini, Cameron Seth

原文摘要

A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.

cs.DS · math.CO

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

Online Metric Matching with Unknown i.i.d. Arrivals

Tsubasa Harada

原文摘要

We study online metric matching with $n$ servers and $n$ requests drawn independently from an unknown distribution. Each request must be matched immediately and irrevocably to an unused server, and the algorithm receives no samples before the process starts. We give a randomized algorithm that is $O((\log\log\log n)^2)$-competitive on arbitrary metric spaces and $O(1)$-competitive on tree metrics. These guarantees match the corresponding bounds for known i.i.d. request distributions in [GGPW19] up to constant factors. More generally, our competitive ratio is $O(α(n))$ whenever the Fair-Bias algorithm introduced in that work has competitive ratio $α(n)$ for known i.i.d. arrivals on the same class of metrics. Consequently, proving that Fair-Bias is constant-competitive on general metrics would also yield a constant-competitive algorithm for unknown i.i.d. arrivals.

cs.DS

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

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields

Tiange Li, Yinan Li, Youming Qiao, Dacheng Tao, Yingjie Wang

原文摘要

In Grochow and Qiao (\emph{SIAM J. Comput.}, 2023), the complexity class Tensor Isomorphism (TI) was introduced and isomorphism problems for groups, algebras, and polynomials were shown to be TI-complete. In this paper, we study average-case algorithms for several TI-complete problems over finite fields, including algebra isomorphism, matrix code conjugacy, and $4$-tensor isomorphism. Our main results reveal a rich landscape of average-case complexities of Tensor Isomorphism problems, despite their equivalence in the worst-case setting. Over the finite field of order $q$, we devise (1) average-case \emph{polynomial-time} algorithms for algebra isomorphism and matrix code conjugacy that succeed for $1/Θ(q)$ fraction of inputs; (2) an average-case \emph{polynomial-time} algorithm for the $4$-tensor isomorphism that succeeds for $1/q^{Θ(1)}$ fraction of inputs; and (3) an average-case \emph{polynomial-time} algorithm for the orthogonal $3$-tensor isomorphism that succeed for $1-1/\poly(n)$ fraction of $n\times n\times n$ tensors. Our main technical contribution is to introduce the spectral properties of random matrices into algorithms for TI-complete problems. This leads to not only new algorithms but also new questions in random matrix theory over finite fields. To settle these questions, we need to extend both the generating function approach as in Neumann and Praeger (\emph{J. London Math. Soc.}, 1998) and the character sum method of Gorodetsky and Rodgers (\emph{Trans. Amer. Math. Soc.}, 2021).

cs.CC · cs.DS · math.PR

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

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni, Ruta Mehta, Parnian Shahkar

原文摘要

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $ω(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

cs.GT · cs.DS

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

Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth

Xuan Chen, Shuangping Li

原文摘要

The low-degree method predicts computational thresholds by asking whether low-degree polynomials can distinguish a planted distribution from a null one. Recent counterexamples by Buhai, Hsieh, Jain, and Kothari (FOCS 2025) and Mao (2026) show that low-degree indistinguishability does not, in general, rule out efficient algorithms, even on noisy inputs. Hsieh, Kane, Kothari, Li, Mohanty, and Tiegel (STOC 2026) asked what it does imply, and showed that for permutation-invariant distributions on $\{0,1\}^n$, low-degree indistinguishability from the uniform distribution implies statistical indistinguishability after noise. In this work, we study the same question for planted subgraphs in sparse random graphs. Let $Q_n=G(n,c/n)$, and let $P_n$ be obtained by planting a uniformly random copy of a deterministic graph $Γ_n$ into an independent sample from $Q_n$. In the supercritical regime $c>1$, we show that if $P_n$ is degree-$D_n$ indistinguishable from $Q_n$ and the treewidth of $Γ_n$ is $o(D_n/\log n)$, then a noisy version of $P_n$ is asymptotically indistinguishable from $Q_n$. In the critical and subcritical regimes $0<c\le 1$, we obtain the same conclusion without any treewidth assumption, provided $D_n=ω(\log n)$. Our proof has two main ingredients. First, we identify the subgraph-count and automorphism factors in the Fourier expansion with counts of isomorphism triples. Second, we cut a tree decomposition of $Γ_n$ into subtrees, which splits each large Fourier support into low-degree pieces that meet at only a few interface vertices, and we use noise to absorb the cost of reassembling them. At and below criticality, we use the low-degree assumption to rule out short cycles and noise to destroy the remaining long ones.

cs.CC · cs.DS · math.PR

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

Online Beck--Fiala Down to Logarithmic Sparsity

Dylan J. Altschuler, Konstantin Tikhomirov

原文摘要

The celebrated (offline) Beck--Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has discrepancy $O(\sqrt d)$. In this note, we consider the {\it online} version of the conjecture. For every fixed $η>0$, we give a randomized online algorithm that achieves $O_η(\sqrt d)$ prefix discrepancy for every fixed sequence of $d$-sparse vectors $a_t\in[-1,1]^n$, except with probability at most \[ C_ηT\exp\left[-\frac{c_ηd}{\log^{2+η}(ed)}\right]. \] In particular, this gives an optimal $O(\sqrt d)$ discrepancy upper bound for $d\geq C_η(\log T)(\log\log T)^{2+η}$. This range of sparsity is optimal up to $\log\log T$ factors. The result also resolves in strong form the {\it online Spencer problem}, corresponding to the case $d = n$. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.

math.CO · cs.DM · cs.DS · math.PR

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

Incremental Open Addressing Has No Time-Space Tradeoff

Martín Farach-Colton, Andrew Krapivin, William Kuszmaul

原文摘要

In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports $O(1)$ worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor $1$). As an intermediate result, we also revisit the problem of constructing an incremental open-addressed hash table that does not perform reordering (does not move elements around over time). In this setting, we show that it is possible to get $O(1)$ amortized expected positive query time together with $O(1)$ worst-case expected insertion time, a combination that was not previously known to be possible.

cs.DS

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

Semidirect sums of tensors and the matrix multiplication exponent

Baitian Li

原文摘要

This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

cs.CC · cs.DS

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

A Cheeger Inequality for Hypergraphs and Its Applications

Raj Kamal, Amitabha Bagchi

原文摘要

Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon-Boppana bound.

math.CO · cs.DS

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

Kadison--Singer in Deterministic Polynomial Time

Ekene Ezeunala, Haotian Jiang

原文摘要

We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.

cs.DS · cs.DM · math.CO · math.FA

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

A Constant-Factor Approximation for Capacitated Facility Location with Outliers

Rajni Dabas

原文摘要

We give a deterministic polynomial-time $(60/11+\eps)$-approximation for metric capacitated facility location with outliers, with arbitrary opening costs and nonuniform hard capacities. The algorithm respects both capacities and the outlier budget. Its guarantee, approximately $5.455$, is close to the best known factor $5+\eps$ for capacitated facility location without outliers. The main ingredient is a local-search comparison for a common rejection penalty that retains the signed difference between the algorithm's and the comparator's rejection counts. Ordinary approximation guarantees for the penalty objective do not provide this comparison. We extend the exchange-forest accounting of Bansal, Garg, and Gupta \cite{BGG18} so that a nonnegative assignment remainder pays for rejection and cancels in the final bound. We then merge two penalty assignments whose served counts bracket the outlier quota. Grouping alternating paths by their terminal facility preserves capacities and shares opening costs. These ingredients give a $(20/3+\eps)$-approximation; starting each penalty run from the preceding solution improves the guarantee to $60/11+\eps$.

cs.DS

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

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators

Édouard Bonnet, Yeonsu Chang

原文摘要

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding specific induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].

cs.DS · cs.DM · cs.LO · math.CO

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

Towards Optimal Multi-draft Speculative Decoding

Zhengmian Hu, Tong Zheng, Vignesh Viswanathan, Ziyi Chen, Ryan A. Rossi, Yihan Wu, Dinesh Manocha, Heng Huang

原文摘要

Large Language Models (LLMs) have become an indispensable part of natural language processing tasks. However, autoregressive sampling has become an efficiency bottleneck. Multi-Draft Speculative Decoding (MDSD) is a recent approach where, when generating each token, a small draft model generates multiple drafts, and the target LLM verifies them in parallel, ensuring that the final output conforms to the target model distribution. The two main design choices in MDSD are the draft sampling method and the verification algorithm. For a fixed draft sampling method, the optimal acceptance rate is a solution to an optimal transport problem, but the complexity of this problem makes it difficult to solve for the optimal acceptance rate and measure the gap between existing verification algorithms and the theoretical upper bound. This paper discusses the dual of the optimal transport problem, providing a way to efficiently compute the optimal acceptance rate. For the first time, we measure the theoretical upper bound of MDSD efficiency for vocabulary sizes in the thousands and quantify the gap between existing verification algorithms and this bound. We also compare different draft sampling methods based on their optimal acceptance rates. Our results show that the draft sampling method strongly influences the optimal acceptance rate, with sampling without replacement outperforming sampling with replacement. Additionally, existing verification algorithms do not reach the theoretical upper bound for both without replacement and with replacement sampling. Our findings suggest that carefully designed draft sampling methods can potentially improve the optimal acceptance rate and enable the development of verification algorithms that closely match the theoretical upper bound.

cs.CL · cs.DS

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

Variable Parameter Analysis for Scheduling One Machine

Nodari Vakhania

原文摘要

In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends on the structure of a given problem instance and tends to have a favorable asymptotic behavior when the size of the input increases. While applying the VPA to an intractable optimization problem with $n$ objects, the exponential-time dependence in enumeration of the feasible solution set is attributed solely to the variable parameter $ν$, $ν<<n$. As opposed to the FPA, the VPA does not imply any restriction on some problem parameters, it rather takes an advantage of a favorable nature of the problem, which permits to reduce the cost of enumeration of the solution space. Our main technical contribution is a variable parameter algorithm for a strongly $\mathsf{NP}$-hard single-machine scheduling problem to minimize maximum job lateness. The target variable parameter $ν$ is the number of jobs with some specific characteristics, the ``emerging'' ones. The solution process is separated in two phases. At phase 1 a partial solution including $n-ν$ non-emerging jobs is constructed in a low degree polynomial time. At phase 2 less than $ν!$ permutations of the $ν$ emerging jobs are considered. Each of them are incorporated into the partial schedule of phase 1. Doe to the results of an earlier conducted experimental study, $ν/n$ varied from $1/4$ for small problem instances to $1/10$ for the largest tested problem instances, so that that the ratio becomes closer to 0 for large $n$s.

cs.DS

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

On the optimality of truncation among binary linear sketches

Robinson D. H. Cung, Adway Girish, Emre Telatar

原文摘要

We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements. We show that under a certain monotonicity condition, simply truncating the input by retaining a subset of its coordinates is optimal among all linear sketches of the same size. In particular, this applies to distributed testing of correlations of binary vectors when they are of opposite signs and evaluating unate Boolean functions on uniformly random inputs. Additionally, given that truncation is optimal, we immediately have lower bounds for arbitrary binary linear sketches. To illustrate this application, we consider the one-way communication complexity of a distributional graph connectivity problem on $n$ vertices and show that truncation, and hence all binary linear sketches, requires $Θ(n \log n)$ bits to achieve constant error, while a nonlinear protocol only requires $O(\log n)$ bits.

cs.DS · cs.CC · cs.IT

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

Unconditional Boolean Dynamic Lower Bounds from Disjointness

Young Kun Ko

原文摘要

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

cs.DS · cs.CC

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

The Hyperclique Hypothesis is False

Nick Fischer

原文摘要

The Hyperclique Hypothesis postulates that, for all constants $k > h \geq 3$, detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices requires time $n^{k-o(1)}$. This hypothesis is false: there is an algebraic algorithm that detects (and even counts) $k$-cliques in $h$-uniform hypergraphs in time $O(n^{(1-ε_h)k})$. Via known reductions, this also refutes the recently proposed $k$-AP Hypothesis. As a consequence, many problems with conditional lower bounds based on these two hypotheses may admit faster algorithms after all. This result is almost entirely due to AI.

cs.DS

查看论文
arXiv ↗PDF ↗