跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1084新增论文
+883其中 AI 相关
+130已有论文修订
+93新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 19:45库内论文最新更新时间:2026-11-18 08:00

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

26,870 已收录论文22,374 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

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

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

A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy

原文摘要

We characterize the single-pass streaming space complexity of Boolean CSP satisfiability in the strict-turnstile model for every fixed constraint language $Γ$ of $k$-ary Boolean relations that is not trivially satisfiable. Constraints can be inserted or deleted with nonnegative multiplicities; satisfiability is decided for those remaining at the end. While Sharma and Velusamy [ESA 2026] characterized insertion-only complexity via non-redundancy (up to logarithmic factors), we show that strict-turnstile complexity is governed by the integer capturing degree. For $R\subseteq\{0,1\}^k$, let $d_R$ be the minimum degree of an integer-coefficient polynomial vanishing exactly on $R$ over the Boolean hypercube, and set $d_Γ=\max_{R\inΓ}d_R$. On polynomial-length streams, we obtain an $O_k(n^{d_Γ}\operatorname{polylog} n)$-space randomized algorithm and an $Ω_k(n^{d_Γ}/\log n)$ lower bound for all algorithms. Moreover, our algorithm outputs a sparse instance preserving every satisfying assignment. This yields, to our knowledge, the first insertion-only versus turnstile separation for streaming CSPs. It also differs from the Fourier-degree characterization of exact optimization by Kol, Paramonov, Saxena, and Yu [ITCS 2023]. For $k\ge3$, $k$-XOR with literals has three distinct space complexities: $\widetildeΘ(n)$ for insertion-only satisfiability, $\widetildeΘ(n^{\lceil k/2\rceil})$ for strict-turnstile satisfiability, and $\widetildeΘ(n^k)$ for exact optimization in either model.

cs.CC

版本更新 · v4arXiv:2409.12566

平均情形距离下的量子信道测试

Quantum Channel Testing in Average-Case Distance

Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, Tom Gur

AI 速读 基于摘要

论文研究量子信道性质测试的复杂度,提出平均情形模仿钻石(ACID)范数,并给出恒等测试与信道层析在ACID距离下的查询复杂度上下界。

quant-ph · cs.CC · cs.DS

查看原文摘要

We study the complexity of testing properties of quantum channels. First, we show that testing identity to any channel $\mathcal N: \mathbb C^{d_{\mathrm{in}} \times d_{\mathrm{in}}} \to \mathbb C^{d_{\mathrm{out}} \times d_{\mathrm{out}}}$ in diamond norm distance requires $Ω(\sqrt{d_{\mathrm{in}}} / \varepsilon)$ queries, even in the strongest algorithmic model that admits ancillae, coherence, and adaptivity. This is due to the worst-case nature of the distance induced by the diamond norm. Motivated by this limitation and other theoretical and practical applications, we introduce an average-case analogue of the diamond norm, which we call the average-case imitation diamond (ACID) norm. In the weakest algorithmic model without ancillae, coherence, or adaptivity, we prove that testing identity to certain types of channels in ACID distance can be done with complexity independent of the dimensions of the channel, while for other types of channels the complexity depends on both the input and output dimensions. Building on previous work, we also show that identity to any fixed channel can be tested with $\tilde O(d_{\mathrm{in}} d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in ACID distance and $\tilde O(d_{\mathrm{in}}^2 d_{\mathrm{out}}^{3/2} / \varepsilon^2)$ queries in diamond distance in this model. Finally, we prove tight bounds on the complexity of channel tomography in ACID distance.

版本更新 · v2arXiv:2610.41180

Quantum query complexity of Hurwitz stability testing

Maxwell Fitzsimmons, Mohamed Serry, Meenu Kumari, Jun Liu

原文摘要

Determining whether every trajectory of the linear system $\dot{x}=Ax$ converges to zero (or, equivalently, whether $A$ is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix $A\in\mathbb{C}^{n\times n}$ is Hurwitz stable, given an exact normalized block-encoding of $A$. The query complexity is characterized in terms of the system dimension $n$ and a supplied lower bound $0<ν\leq ω_A$ on the imaginary-axis distance $ω_A:=\min_{t\in\mathbb{R}}σ_{\min}(A-\mathrm{i}tI)$, where $σ_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $Ω(\sqrt{n}/ν)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $ω_A$, we encode an approximation of the right-half-plane spectral projector $\operatorname{sign}^+(A):=(I+\operatorname{sign}(A))/2$ as a block of a matrix inverse, where $A$ is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a $(β,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $Θ(β\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}ν^{-2}\log(\sqrt{n}/ν))$ queries in the general case, and $O(\sqrt{n}ν^{-1}\log n)$ when $A$ is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.

quant-ph · cs.CC

版本更新 · v5arXiv:2508.18104

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

Robert Scheffler

原文摘要

We consider two different problem families that deal with domination in graphs. On the one hand, we focus on dominating sequences. In such a sequence, every vertex dominates some vertex of the graph that was not dominated by any earlier vertex in the sequence. The problem of finding the longest dominating sequence is known as $\mathsf{Grundy~Domination}$. Depending on whether the closed or the open neighborhoods are used for domination, there are three other versions of this problem: $\mathsf{Grundy~Total~Domination}$, $\mathsf{L\text{-}Grundy~Domination}$, and $\mathsf{Z\text{-}Grundy~Domination}$. We show that all four problem variants are $\mathsf{W[1]}$-complete when parameterized by the solution size. On the other hand, we consider the family of zero forcing problems which form the parametric duals of the Grundy domination problems. In these problems, one looks for the smallest set of vertices initially colored blue such that certain color change rules are able to color all other vertices blue. It has been shown that the dual of $\mathsf{Z\text{-}Grundy~Domination}$, known as $\mathsf{Zero~Forcing~Set}$, is in $\mathsf{FPT}$ when parameterized by the treewidth or the solution size. We extend the treewidth result to the other three variants of zero forcing and their respective Grundy domination problems. Our algorithm also implies an $\mathsf{FPT}$ algorithm for $\mathsf{Grundy~Domination}$ when parameterized by the number of vertices that are not in the dominating sequence. In contrast, we show that $\mathsf{L\text{-}Grundy~Domination}$ is $\mathsf{W[1]}$-hard for that parameter.

cs.CC · cs.DM · cs.DS · math.CO

新论文 · v1arXiv:2611.18201

Go under Chinese Rules with a Succinct Game History is Complete for Exponential Space

Markus Bläser, Felix Czerner

原文摘要

The complexity of games is a central topic in combinatorics, algorithms, and computational complexity theory. It asks how difficult it is to determine the winner of a combinatorial game under optimal play. Many games, such as Hex or Othello, are PSPACE-complete: the game tree has polynomial depth, so the game can be decided in PSPACE. However, some games allow exponentially long plays, for instance Chess (without a generalized 50-move rule) or Go under Japanese rules; these are complete for exponential time. To prevent infinite games, some games employ a no-repetition rule (super-ko rule), for instance Go under Chinese rules. Robson (1984) proved that Chess and Checkers with a no-repetition rule are even harder: deciding whether the first player has a winning strategy is EXPSPACE-complete. Since then, it has been an open problem whether Go with a no-repetition rule is EXPSPACE-complete, too. The complexity of a game under a no-repetition rule is typically interpreted as follows: given a board position, decide whether the first player has a winning strategy such that no repetition occurs from that position on. We introduce the concept of a succinct game history: a Boolean circuit that, given a board position, outputs 1 if the position is in the game history and 0 otherwise. It serves as a "judge" that tells the players whether a move is illegal because it creates a repetition. We prove that deciding whether Black has a winning strategy in Go with a no-repetition rule is EXPSPACE-complete when the game history is given succinctly. Moreover, the starting position in our hardness proof is reachable by legal gameplay, which has not always been the case in prior proofs.

cs.GT · cs.CC

新论文 · v1arXiv:2611.18084

On Applications of Polynomial-Time Group Isomorphism Algorithm

Wenkang Zhang, Zhinan Wang, Jincheng Zhuang

原文摘要

The group isomorphism problem is a fundamental problem in computational group theory and is closely related to many other problems. Recently, Qiao and Zhang proposed a polynomial-time algorithm for finite group isomorphism in the multiplication-table model that computes the coset of all isomorphisms. Based on the algorithm of Qiao and Zhang, we study applications to finite associative ring isomorphism, bilinear map isotopism over finite commutative rings and free three-tensor isomorphism over finite commutative rings. First, we obtain a polynomial-time algorithm that returns the coset of all isomorphisms for finite associative rings. Second, we extend efficient isotopism and isomorphism algorithms for bilinear maps and free three-tensors from fields to general finite commutative rings.

cs.CC

新论文 · v1arXiv:2611.17845

Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs

Tianhang Lu, Runtian Ren, Shengcai Liu

原文摘要

We determine the dense worst-case quantum query complexity of exact minimum multicut on simple unweighted undirected graphs. With at most $k$ explicit demand pairs, our adjacency-array algorithm uses $\OO(n+\min\{m,n^{3/2}\sqrt{k}\})$ queries; a matching lower bound holds for every $1\le k\le\lfloor n/2\rfloor$ and sufficiently large $n$, with constants uniform in $k$. In particular, the $k=1$ case gives an $\OO(n^{3/2})$ query algorithm for prescribed $s$--$t$ cut. The upper bound combines degree-sensitive spectral estimates of local improvement with refinement by unions of label classes. These steps retain every original optimum and permit exact acquisition without an additional label-count factor. Separately, we prove an $Ω(n^{3/2})$ global minimum-cut lower bound on dense connected graphs, matching the existing upper bound up to polylogarithmic factors. It holds for the value and for any optimum shore, even with known degrees and sorted neighbor arrays; regular hard instances have balanced optimum cuts. Both lower bounds use degree-preserving switches and classify optimum outputs across a hidden threshold. Our upper bound concerns input queries, not total running time: computation on acquired data may be exponential, even in the single-demand case. Matching bounds at each prescribed sparse edge count are not established.

cs.DS · cs.CC

新论文 · v1arXiv:2611.17804

Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types

Tianci Peng, Shiqi Hou, Xiaoyang Dong

原文摘要

We determine the bounded-error quantum query complexity of finding one $r$-collision in an $N$-input function of prescribed type, which specifies all equality-class sizes. For every fixed maximum class size and collision order, we give a tight bound as the maximum of scales determined by the numbers of classes of size at least $2,\ldots,r$. The lower bound holds for a uniformly random function of that type, and a matching algorithm succeeds on every such function. No intermediate class size is required to occur, and every feasible output alphabet is allowed. The characterization connects the abundant-collision regime associated with set equality to the sparse-target regime of $k$-distinctness. In particular, finding the unique $(k+1)$-collision in type $(k^n,k+1)$ has complexity $Θ_k(N^{3/4-1/[4(2^{k+1}-1)]})$, where $N=kn+k+1$, resolving an open problem of Belovs. For the lower bound, we introduce a filtered compressed permutation oracle that projects onto a harmonic database subspace after each complete function query. Its $O(T/N)$ comparison error over $T$ queries overcomes the square-root limitation of the unfiltered process. Hidden capacity extensions and moment estimates retain the populations at each intermediate collision order. Matching upper bounds use sampled collision lists and colored adaptive learning graphs, with a coherent decision-to-search conversion that avoids logarithmic overhead. We also give an alternative nested quantum-walk algorithm for three-collision search, matching the bound up to polylogarithmic factors.

quant-ph · cs.CC

版本更新 · v3arXiv:2501.04151

Efficient LP warmstarting for linear modifications of the constraint matrix

Guillaume Derval, Bardhyl Miftari, Damien Ernst, Quentin Louveaux

原文摘要

We consider the problem of computing the optimal solution and objective value of a linear program whose constraint matrix changes linearly with a parameter, for a predefined set of values of this parameter. Based on the information given by a precomputed basis, we present three efficient LP warm-starting algorithms, based on the eigenvalue decomposition, the Schur decomposition and the Hessenberg decomposition, to evaluate the optimal solution and optimal objective value of these problems. The three algorithms have an overall complexity of $O(pm^2+pmn)$ where $m$ (resp. $n$) is the number of constraints (resp. variables) of the original problem and $p$ the number of parameter values after an initial preprocessing step. We also provide theorems related to the optimality conditions to verify when a basis is still optimal. When the perturbation of the basis matrix has a low rank $ρ$, as is often the case in practice, we then reduce all the computations to a $ρ\timesρ$ matrix built with $ρ$ solves with the factorization of the basis maintained by the simplex solver; with it, we compute, in each direction, an interval on which the basis is guaranteed to remain optimal, together with a bound on the objective. In practice, these intervals are close to the exact ones, and they remain useful for degenerate bases. We also propose a matrix-free method based on shifted Krylov subspaces. Numerical experiments on 398 instances built from real models, with up to 349,120 constraints, assess the accuracy, the cost and the range of applicability of all the methods. On the interval on which a basis remains optimal, once this interval is known, the low-rank and Krylov methods compute the optimal objective value 117 to 304 times faster than a warm start of the solver, in median.

math.OC · cs.CC

新论文 · v1arXiv:2611.17312

锦标赛均衡集在遗传唯一性下仍是PSPACE完全的

The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

Ethan Dickey, Athina Terzoglou

AI 速读 基于摘要

作者证明锦标赛均衡集(TEQ)的成员判定问题是PSPACE完全的,且该困难性在Schwartz所猜想的遗传唯一性条件下依然成立。

cs.GT · cs.CC

查看原文摘要

The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.

新论文 · v1arXiv:2611.17252

播下难解性的种子:Kalah 是 PSPACE 完全的

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

Ethan Dickey, Ethan Mader

AI 速读 基于摘要

作者研究棋盘规模可变的 Kalah 游戏,证明判定指定玩家能否强制获胜是 PSPACE 完全的。

cs.CC · cs.GT · math.CO

查看原文摘要

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

版本更新 · v2arXiv:2611.05951

成员特定容忍度下的社区搜索

Community Search under Member-Specific Tolerances

Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng

AI 速读 基于摘要

研究每个成员对位置差异有各自容忍度时的社区搜索问题,提出纬度一致社区(LCC)模型及精确与近似算法。

cs.SI · cs.CC · cs.DB

查看原文摘要

We study community search when each member has its own tolerance for differences in position, as when members of a group interact repeatedly and influence one another. A latitude-consistent community (LCC) contains the query vertex, is connected, has minimum degree at least k, and bounds its diameter by the smallest member tolerance. The bound is exactly the condition under which every interaction in a connected closed group stays accepted under bounded-confidence dynamics for every choice of positive weights. It also prevents rejection under social-judgment dynamics, whereas the pairwise condition and other natural relaxations preserve neither guarantee. Finding a maximum LCC is NP-hard even in the plane, and with unbounded dimension, deciding whether an LCC exists is NP-complete for every fixed k>=2. LatSweep fixes the answer's smallest tolerance and turns the coupled bound into a best-first sweep over candidate thresholds, yielding an exact branch-and-bound algorithm, a (1,2)-bicriteria approximation and two feasible heuristics. Across eight graphs with up to 1.8 billion edges, six with synthetic positions and tolerances, the exact algorithm proves optimality on all but 9 of 3,700 efficiency queries; in a shared implementation on two large graphs, its branch-and-bound solver proves more queries than a reimplemented maximum-(k,r)-core algorithm, a mixed-integer program and CP-SAT. In simulations of closed groups, LCC groups keep every accepted interaction under uneven influence, whereas 3-40% of pairwise-compatible groups lose some. On three location-based networks, tolerance-agnostic groups often place another member's home beyond a member's estimated travel radius. Enforcing every member's tolerance causes no measurable loss of co-visits relative to spatial communities of the same size. Relative to the larger pairwise-compatible groups, it can cause a size-adjusted loss.

版本更新 · v2arXiv:2609.32007

面向模型评估的交互式邻近性证明

Interactive Proofs of Proximity for Model Evaluation

Geoffroy Couteau, Nikolas Melissaris, Tamara Paris

AI 速读 基于摘要

研究资源受限验证者借助不可信证明者(通常是模型所有者)认证模型在未知输入分布下统计性质的交互式邻近性证明(IPP),聚焦双亚线性复杂度与(加权)Hamming重量性质。

cs.CC

查看原文摘要

We study interactive proofs of proximity (IPPs) for model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation separates sampling the input distribution from querying the model and evaluating its output; distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and allows the prover and verifier to use different evaluators. We focus on doubly-sublinear IPPs, where both the verifier and honest prover use sublinear resources, and on (weighted) Hamming weight properties. For ordinary Hamming weight, we give a tolerant doubly-sublinear IPP. For completeness and soundness radii $\varepsilon_c<\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, a logarithmic-round instantiation uses $\widetilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum (ITCS 2025). We prove matching query lower bounds up to polylogarithmic factors. For distribution-weighted Hamming weight, black-box sampling requires $Θ(1/g^2)$ verifier samples but only $\widetilde{O}(1/g)$ evaluations; the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access, the problem reduces to ordinary Hamming weight, yielding $\widetilde{O}(1/g)$ calls and evaluations. If the parties' evaluators disagree arbitrarily on a $ρ$-fraction of the distribution and by at most $γ$ elsewhere, our protocols remain doubly sublinear whenever $g>2κ$, where $κ=ρ+(1-ρ)γ$. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

新论文 · v1arXiv:2611.16779

Computation with Backward Feedback: Power, Observation, and Cost

Saman Farhat, Farzad Didehvar

原文摘要

How much can a computation gain by passing information back to an earlier stage, and how soon can an observer obtain the answer? We study deterministic programs whose runs are accessed at randomly selected stages. A program keeps a register, a finite block of memory. A random clock selects the current stage; each tick takes a random step, with a law fixed independently of input, program and register. When the clock moves backward, the register contents at the stage it leaves start a new run, and the clock continues where it lands. Equilibrium readout requires a distribution of clock position and register that one tick leaves unchanged, and a correct final answer under every such distribution. For bounded steps in both directions with negative average, we obtain an exact classification at each polynomial scale s. If running time and register length are both O(s), feedback gives exactly nondeterministic space O(s); without transmission the class is deterministic time O(s), which is strictly smaller. An observer that starts at stage zero with an all-zero register, reads sequentially and never accepts a nonmember sees, with fewer ticks than any exponential, only languages fixed by a bounded input prefix. Exponentially many ticks reveal every linear-time language. For a clock moving one step up or down, we bound the wait for useful backward moves and the rate of random erasures a stored counter tolerates. The results separate the power of feedback at equilibrium, observation from a fixed start, and the cost of obtaining and keeping information.

cs.CC

新论文 · v1arXiv:2611.16746

Topological Entropy of Group Cellular Automata is Effectively Computable

Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara

原文摘要

Topological entropy is a fundamental invariant of dynamical systems, quantifying their complexity. For cellular automata, however, determining topological entropy is generally algorithmically intractable. We study group cellular automata, namely cellular automata over a finite group alphabet whose global map is a group endomorphism. In dimension one, we decompose topological entropy into two one-sided components describing information propagating from the left and from the right in space--time. We introduce finite families of left and right traces and prove that the entropy is the sum of their growth rates. Hence, the entropy is completely determined by the growth rate of a fixed-width family of space--time patterns. This reduction from arbitrarily large windows to uniformly bounded width yields an effective procedure for computing the entropy. In particular, the entropy of every one-dimensional group cellular automaton is the logarithm of a positive integer. Using Pontryagin duality and the Bridge Theorem between topological and algebraic entropy, we also derive an explicit formula for linear cellular automata over $(\mathbb{Z}/p\mathbb{Z})^n$ in terms of their characteristic polynomial. Moreover, in every dimension $D\geq 2$, a group cellular automaton is either equicontinuous with zero entropy or sensitive to initial conditions with infinite entropy. Combined with decidability of equicontinuity, this implies that topological entropy is effectively computable from the local rule in every dimension. Thus, group cellular automata form a natural nontrivial class in which algebraic structure restores computability of topological entropy.

cs.CC · math.DS

版本更新 · v2arXiv:2606.21103

On the Reachability Problem on Monoid-Labelled Undirected Graphs

Nagashri Krishnakumar, Harshil Mittal, Jayalal Sarma

原文摘要

The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid $M$ (more generally, groupoids or magmas) captures the classes $\sf{L}$ and $\sf{NL}$. Given a graph $G(V, E)$ labelled by $φ~\colon E \to M$, $s,t \in V$ and an accepting subset $F \subseteq M$, the problem asks to test whether there is a walk $P$ from $s$ to $t$ in $G$ where $φ(P) \in F$. Ramaswamy et al. (2019) studied the variant where the accepting element is part of the input for aperiodic monoids and groups. Motivated by the success in designing space-bounded algorithms for the undirected graph reachability problem, we study the labelled reachability problem when the accepting set is also fixed. This reveals finer complexity bounds and dichotomies for the problem based on the monoid and the accepting set. Previous results imply that the problem is in $\sf{L}$ for any finite accepting subset when $M$ is a group or belongs to $\sf{DA}$. We prove the following (for finite monoids): 1) For any monoid $M$, the problem is in $\sf{L}$ when the accepting element is the identity of $M$. If the accepting element is an idempotent, under suitable constraints, the problem is $\sf{NL}$-hard. 2) For any commutative monoid $M$, the problem is in $\sf{L}$ for all $F \subseteq M$. 3) For any $\mathcal{L}(\mathcal{R})$-commutative union-of-groups (UoG) monoid $M$, the problem is in $\sf{L}$ for all $F\subseteq M$. We show deterministic logspace algorithms for UoG monoids that are neither $\mathcal{L}$-commutative nor $\mathcal{R}$-commutative, under certain constraints. 4) For the monoids $\sf{BA_2}$ and $\sf{U}$, we show a dichotomy: for all $F \subseteq M$, the problem is either $\sf{NL}$-complete or in $\sf{L}$. Our results exploit the connection between Green's relations in the UoG monoids and the properties of the product graph (a graph introduced by Ramaswamy et al. (2019)).

cs.CC

新论文 · v1arXiv:2611.16729

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski, Stanislav Živný

原文摘要

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain $D$ and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let $c_Γ$ be the size of the largest set $S\subseteq D$ such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of $S$. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value $c_Γ$. (1) The problem can be solved in time $(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 0$, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

cs.DS · cs.CC

新论文 · v1arXiv:2611.16412

Exact Quantum Algorithms for Composed Boolean Functions

Gagan Chiruvella, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh

原文摘要

We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$ Q_E(f\circ g)=O\!\left(mD+Q_E(f)Q_{1/(4D)}(g)\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction. We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\sqrt2)^{k(1+o(1))}$ queries asymptotically. More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\}$ and prove $Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with $s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\ldots$. A second construction gives $R \ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. We also allow different inner functions and give analogous quantitative separations in quantum communication.

cs.CC · quant-ph

新论文 · v1arXiv:2611.16192

Weak Composition Theorems for Randomized Communication

Pachara Sawettamalya

原文摘要

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

cs.CC

新论文 · v1arXiv:2611.16138

Individually Fair Facility Location

Rajni Dabas, Samir Khuller, Milind Maiti

原文摘要

We study individually fair facility location, where each client must connect to an open facility within a prescribed radius and the objective is to minimize total opening and connection cost. We show that preserving the radii changes the approximability of metric facility location fundamentally. For every fixed radius violation below three, no deterministic polynomial-time algorithm achieves a sublogarithmic cost factor unless $\mathrm{P}=\mathrm{NP}$. The hardness holds with uniform opening costs and uniform radii. It contradicts the strict-fairness constant-factor guarantee recently claimed by Liu, Xu, and Zhang [Theory of Computing Systems, Vol. 70 (2026)]. We then establish a positive result for arbitrary client radii. We give a randomized polynomial-time algorithm that has cost at most $1.725$ times the strictly fair optimum and serves every client within three times its fair radius (in the Appendix we show how this can be de-randomized). We use the approach of Byrka, Srinivasan and Swamy [IPCO 2010]. The facility-location radius factor three is therefore optimal among deterministic polynomial-time algorithms with constant cost factor, unless $\mathrm{P}=\mathrm{NP}$. Experiments on real-world data indicate that the worst case radius bound is rarely realized in practice: the algorithm serves over 99.8% of clients within their stated radius, and never beyond 1.5 times it. Our code is available at https://github.com/milindmaiti/IFFL_Implementation.

cs.DS · cs.CC

新论文 · v1arXiv:2611.16096

The Ultimate Karp-Lipton Collapse

Edward A. Hirsch, Ilya Volkovich

原文摘要

Karp and Lipton proved that if $NP\subseteq P/poly$, then $PH$ collapses. A long line of work pushed the collapse to smaller classes. In particular, Chakaravarthy and Roy obtained two such collapses, to (apparently) incomparable classes $O_2^P$ and $P^{prMA}$. We united them earlier by a collapse to the input-oblivious version $P^{prOMA}$ of $P^{prMA}$, which is contained in both; and, jointly with Williams, to a slightly smaller class. Two other deepest known collapses are to $ZPP^{ONP}$ (following from Köbler and Watanabe) and to $OL_2^P$ (proved in this paper). We unite the three collapses by a collapse to a class contained in all of them. We use a three-stage computational model OGTD (oblivious generator-tester-decoder): a polynomial-time generator with an oracle computes an advice string from $1^n$, a tester certifies it, and a polynomial-time decoder uses it (it is the only one that sees the actual input). Let $OM$ be the class of OGTD languages defined by a restricted version of $prOMA$ as the generator's oracle, by a co-$ONP$ tester, and a $P$ decoder. We show that it is contained in the three collapse classes above and prove that $PH$ collapses to $OM$ under $NP\subseteq P/poly$. The collapse also holds for an unambiguous version of $OM$. All these input-oblivious collapse classes lie in $P^{prSBP}$, and so do even the non-input-oblivious versions $P^{prMA}$, $L_2^P$ and $S_2^P$: we prove that $P^{prS_2^P}\subseteq P^{prSBP}$. This strengthens the containment $S_2^P\subseteq P^{prAM}$ of Chakaravarthy and Roy and our earlier containment $L_2^P\subseteq P^{prSBP}$. The proof unites the Goldreich-Wigderson-type procedure of Chakaravarthy and Roy with our earlier approximate-counting technique. Its input-oblivious counterpart concerns $O_2^P$, the first collapse class of Chakaravarthy and Roy: every language in $O_2^P$ has polynomial-size circuits constructible in $FP^{prSBP}$.

cs.CC

新论文 · v1arXiv:2611.15803

Statistical-to-computational gaps in central limit theorems for high-dimensional tensors

Debsurya De, Dmitriy Kunisky

原文摘要

We study high-dimensional central limit theorems (CLTs) as hypothesis testing problems, comparing the number of summands needed for statistical and computational indistinguishability of the normalized sum from the limiting Gaussian distribution as the dimension and number of summands grow together. For the off-diagonal entries of sums of i.i.d. rank-one tensors formed from standard Gaussian vectors (equivalently, the problem of distinguishing Wigner from Wishart tensors), we prove total variation bounds sharpening previous estimates of Mikulincer (2020) and give matching polynomial-time tests. This shows that the statistical and computational thresholds coincide for this CLT, contrary to a proposal by Kunisky, Moore, and Wein (2024). On the other hand, we also show that, for tensors of order at least three, sufficient Gaussian dilution of the summands by adding independent Gaussian noise and rescaling gives a CLT model with a statistical-to-computational gap (in the above setting and ones with more general rank-one summand distributions). To the best of our knowledge, such a phenomenon has not been observed before in any high-dimensional CLT. In particular, in the relevant parameter regimes, we show that a brute-force search achieves strong detection, while polynomials of degree up to $n^{Ω(1)}$ cannot achieve strong separation. The latter lower bounds control low-degree $χ^2$-divergences by a novel method based on cumulant generating functions, and we further illustrate the use of these tools by applying them to masked tensor CLT models where only a prescribed subset of tensor entries is revealed.

math.ST · cs.CC · math.PR

新论文 · v1arXiv:2611.15784

Small Maximum Likelihood on Fixed Cavender-Farris-Neyman Trees: An Approximation Scheme and Limits to Fully Polynomial Approximation

Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei

原文摘要

Small Maximum Likelihood fits the edge substitution probabilities of a given phylogenetic tree to an observed alignment, summing over the unobserved ancestral states. For the binary Cavender--Farris--Neyman model, we assume a uniform root and an edge-specific substitution probability $p_e\in[0,\tfrac12]$ for each edge $e$, shared across all alignment sites. We give a deterministic polynomial-time approximation scheme. The algorithm achieves a factor of $1+\varepsilon$ for both the negative log likelihood and the loss after subtracting the uniform-root contribution. Its main step fixes ancestral sequences at one periodically spaced class of depths while summing over all remaining ancestors. A posterior entropy bound controls the cost of this restriction, and dynamic programming optimizes the resulting components over a finite parameter grid. We also give a randomized reduction from Clique showing that an FPTAS returning feasible rational edge probabilities would imply $RP=NP$. These results separate fixed-accuracy approximation from fully polynomial approximation for the same fixed-tree model.

cs.DS · cs.CC

版本更新 · v3arXiv:2610.34273

Asymptotic Rank of Weighted Graph Tensors via Completely Positive Bounds

Huanyi Zhou

原文摘要

We give a conic upper bound on the asymptotic rank of every weighted graph tensor over every field. If $W$ is the logarithmic edge-weight matrix of its dimension matrix $Q$, then $$ \operatorname{MaxCut}(W)\le\log_2\operatorname{\widetilde R}_{\mathbb F}(\mathsf{WT}(Q))\le U_{\operatorname{CP}}^Δ(W). $$ Here $U_{\operatorname{CP}}^Δ(W)$ maximizes $\sum_{1\le i<j\le n}W_{i,j}P_{i,j}$ over nonnegative symmetric zero-diagonal matrices $P$ such that $J-2P$ is copositive and $P_{i,j}\le P_{i,k}+P_{k,j}$ for all distinct vertices. The matrix $J$ is all-one, and copositivity means nonnegativity of the quadratic form on nonnegative vectors. Our starting point extends OpenAI's polynomial multiplication method and its subsequent arbitrary-field developments from three tensor legs to arbitrary order. We prove $$ \left\lfloor\frac{n^2}{4}\right\rfloor\le\log_2\operatorname{\widetilde R}_{\mathbb F}(\mathsf{GT}_2(K_n))\le\frac{n^2}{4}. $$ The edge exponent is at most $n/(2(n-1))$ and tends to the optimal value $1/2$, improving the previous Coppersmith--Winograd bounds and answering Question 1.3.1 of Christandl, Vrana, and Zuiddam. The bounds coincide for every even $n$. For every odd $m\ge3$, the theorem gives $\log_2\widetilde R_{\mathbb F}(\mathsf{GT}_2(C_m))\le m-1+1/(m+1)$, improving the previous cycle bound with a gap of only $1/(m+1)$ above the maximum cut. On weighted triangles, the program recovers the rectangular matrix multiplication curve of Uzna'nski and Amanov, van den Berg, and Zuiddam. The CP and semidefinite programs, with or without path constraints, all have value $9/4$ on the unweighted triangle, giving this upper bound a natural conic interpretation. Further applications give explicit bounds for complete multipartite graphs, split graphs, and wheels, including new cases of maximum-cut equality.

cs.CC · cs.DM · math.CO

版本更新 · v6arXiv:2009.03996

Combining Determinism and Indeterminism

Michael Stephen Fiske

原文摘要

Our goal is to construct mathematical operations that combine indeterminism measured from quantum randomness with computational determinism so that non-mechanistic behavior is preserved in the computation. Formally, some results about operations applied to computably enumerable (c.e.) and bi-immune sets are proven here, where the objective is for the operations to preserve bi-immunity. While developing rearrangement operations on the natural numbers $\mathbb{N}$, we discovered that the bi-immune rearrangements generate an uncountable subgroup of the infinite symmetric group (Sym$(\mathbb{N})$) on the natural numbers. This new uncountable subgroup is called the bi-immune symmetric group. The bi-immune symmetric group contains the finitary symmetric group on the natural numbers, and consequently is highly transitive. Furthermore, the bi-immune symmetric group is dense in Sym$(\mathbb{N})$ with respect to the pointwise convergence topology. Moreover, the bi-immune symmetric group contains permutations that are a single infinite cycle on all of $(\mathbb{N})$, even though every one of its generators has only finite orbits. Using an invariant called the {\it crossing number}, we also prove that the bi-immune symmetric group is a meager subset and a proper subgroup of Sym$(\mathbb{N})$.

math.LO · cs.CC · cs.CL · math.GR

版本更新 · v3arXiv:2412.03395

An even simpler hard variant of Not-All-Equal 3-SAT

Andreas Darmann, Janosch Döcker, Britta Dorn

原文摘要

We investigate Positive Not-All-Equal 3-Sat under a strong structural restriction and delineate a sharp tractability threshold. In particular, we consider the restriction of Positive Not-All-Equal 3-Sat to instances that simultaneously satisfy the following properties: (i) the clauses can be decomposed into a disjoint union of $k$ partitions of the variable set, and (ii) the collection of clauses is linear, that is, each pair of distinct clauses shares at most one variable. We show that, under these conditions, Positive Not-All-Equal 3-Sat remains NP-complete for any fixed $k \geq 4$. On the positive side, we prove that for $k \leq 3$, the problem is in P and, notably, all such instances are not-all-equal-satisfiable. Our results do not only show robustness of NP-completeness despite the strong structure imposed but also have implications for hypergraph coloring. In particular, by the well-known correspondence between Positive Not-All-Equal 3-Sat and hypergraph coloring, we obtain the following corollary of our results: For $k\geq 4$, Bicolorability is NP-complete for linear 3-uniform $k$-regular hypergraphs even if the edges are given as a decomposition into $k$ perfect matchings; with the same restrictions, for $k \leq 3$ Bicolorability is in P, and all such hypergraphs are bicolorable. In addition, we show that loosening the restriction to 3-clauses by also allowing 2-clauses shifts the above-mentioned tractability threshold. Moreover, we deduce that every instance of Positive Planar Not-All-Equal Sat with at least three distinct variables per clause is nae-satisfiable. Besides, for Linear Not-All-Equal 3-Sat we derive a computational complexity dichotomy with respect to the number of variable appearances.

cs.CC

新论文 · v1arXiv:2611.15128

Affine Combiners for Reed-Solomon Proximity Gaps

Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, Kai Zhe Zheng

原文摘要

Reed-Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius. We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(α+βx)g(x)$, where $α,β$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=ρn$, fixed $ρ\in(0,1)$ and $0<η<1-\sqrtρ$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrtρ+η)n\rceil$, with error $O_{ρ,η}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding. For $q\ge n^2$, our error is $O_{ρ,η}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $Ω_{ρ,η}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $Ω_{ρ,η}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed-Muller codes on subfield grids, obtaining MCA error $O_{ρ,η,k}(q^{-k})$ for fixed $ρ,η,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$.

cs.IT · cs.CC · cs.CR

新论文 · v1arXiv:2611.15074

Tokenization: Hardness and Bicriteria Approximation Algorithms

Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran

原文摘要

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

cs.DS · cs.AI · cs.CC

版本更新 · v2arXiv:2611.06658

The determinantal complexity of the 4*4 permanent is 15

Karthik Sheshadri

原文摘要

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

cs.CC