Computational Complexity
See recent articles
Showing new listings for Monday, 16 November 2026
- [1] arXiv:2611.17690 [pdf, html, other]
-
Title: Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMsSubjects: Computational Complexity (cs.CC)
We show that read-$k$ Probabilistic Turing Machines with bounded space $S$ and running time $T$ can be simulated by read-once Probabilistic Turing Machines with error $\varepsilon$, running in space $ O(k^2 (S + \log (n+ T)) + \log (1/\epsilon))$ and time $\frac{1}{\varepsilon} \cdot 2^{O\left(k^2\left(S+\log(n+T) \right)\right)}$. As a direct consequence we show that read-$k$ $\mathsf{BPL}$ is equal to $\mathsf{BPL}$, for any constant $k$. Recently OpenAI announced that $\mathsf{BPL} = \mathsf{L}$. If this is true then our result immediately implies that read-$k$ $\mathsf{BPL}$ is equal to $\mathsf{L}$.
- [2] arXiv:2611.18084 [pdf, html, other]
-
Title: On Applications of Polynomial-Time Group Isomorphism AlgorithmComments: 10 pagesSubjects: Computational Complexity (cs.CC)
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.
New submissions (showing 2 of 2 entries)
- [3] arXiv:2611.17804 (cross-list from quant-ph) [pdf, html, other]
-
Title: Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded TypesSubjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
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 $\Theta_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. - [4] arXiv:2611.17845 (cross-list from cs.DS) [pdf, html, other]
-
Title: Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense GraphsSubjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
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 $\Omega(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.
- [5] arXiv:2611.18201 (cross-list from cs.GT) [pdf, html, other]
-
Title: Go under Chinese Rules with a Succinct Game History is Complete for Exponential SpaceComments: A preliminary version of this paper appears in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)
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.
Cross submissions (showing 3 of 3 entries)
- [6] arXiv:2508.18104 (replaced) [pdf, html, other]
-
Title: On the Parameterized Complexity of Grundy Domination and Zero Forcing ProblemsComments: version published in the Journal of Computer and System SciencesJournal-ref: Journal of Computer and System Sciences 164, Article 103875 (2027)Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
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. - [7] arXiv:2409.12566 (replaced) [pdf, html, other]
-
Title: Quantum Channel Testing in Average-Case DistanceSubjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (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 $\Omega(\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. - [8] arXiv:2501.04151 (replaced) [pdf, html, other]
-
Title: Efficient LP warmstarting for linear modifications of the constraint matrixSubjects: Optimization and Control (math.OC); Computational Complexity (cs.CC)
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 $\rho$, as is often the case in practice, we then reduce all the computations to a $\rho\times\rho$ matrix built with $\rho$ 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.
- [9] arXiv:2610.41180 (replaced) [pdf, html, other]
-
Title: Quantum query complexity of Hurwitz stability testingComments: 36 pages, including appendices; 1 figure, 1 tableSubjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC)
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<\nu\leq \omega_A$ on the imaginary-axis distance $\omega_A:=\min_{t\in\mathbb{R}}\sigma_{\min}(A-\mathrm{i}tI)$, where $\sigma_{\min}(A)$ is the smallest singular value of $A$. We prove a query-complexity lower bound of $\Omega(\sqrt{n}/\nu)$, which holds even when $A$ is restricted to be real and diagonal. For general matrices with nonzero $\omega_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 $(\beta,b,1/(4\sqrt{n}))$-block-encoded projector matrix (like $\operatorname{sign}^+(A)$) is zero or not; for constant success probability, it has complexity $\Theta(\beta\sqrt{n})$. When the zero test is applied to specific approximations of $\operatorname{sign}^+(A)$, this yields an upper bound of $O(\sqrt{n}\nu^{-2}\log(\sqrt{n}/\nu))$ queries in the general case, and $O(\sqrt{n}\nu^{-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.