JournalTOCs

Theory of Computing Systems
Journal Prestige (SJR): 0.372

Citation Impact (citeScore): 1
Number of Followers: 2

Hybrid journal (It can contain Open Access articles)
ISSN (Print) 1433-0490 - ISSN (Online) 1432-4350
Published by Springer-Verlag

[2467 journals]

Correction to: Submodular Functions and Rooted Trees
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  PubDate: 2023-04-01
On the Transformation of LL(k)-linear to LL(1)-linear Grammars
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract It is proved that every LL(k)-linear grammar can be transformed to an equivalent LL(1)-linear grammar. The transformation incurs a blow-up in the number of nonterminal symbols by a factor of m2k−O(1), where m is the size of the alphabet. A close lower bound is established: for certain LL(k)-linear grammars with n nonterminal symbols, every equivalent LL(1)-linear grammar must have at least \(n \cdot (m-1)^{2k-O(\log k)}\) nonterminal symbols.
  PubDate: 2023-04-01
Local Deal-Agreement Algorithms for Load Balancing in Dynamic General
Graphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract We study the classic load balancing problem on dynamic general graphs, where the graph changes arbitrarily between the computational rounds, remaining connected with no permanent cut. A lower bound of Ω(n2) for the running time bound in the dynamic setting, where n is the number of nodes in the graph, is known even for randomized algorithms. We solve the problem by deterministic distributed algorithms, based on a short local deal-agreement communication of proposal/deal in the neighborhood of each node. Our synchronous load balancing algorithms achieve a discrepancy of ðœ– within the time of \(O(nD \log (nK/\epsilon ))\) for the continuous setting and the discrepancy of at most 2D within the time of \(O(n D \log (n K/D))\) and a 1-balanced state within the additional time of O(nD2) for the discrete setting, where K is the initial discrepancy, and D is a bound for the graph diameter. Also, the stability of the achieved 1-balanced state is studied. The above results are extended to the case of unbounded diameter, essentially keeping the time bounds, via special averaging of the graph diameter over time. Our algorithms can be considered anytime ones, in the sense that they can be stopped at any time during the execution, since they never make loads negative and never worsen the state as the execution progresses. In addition, we describe a version of our algorithms, where each node may transfer load to and from several neighbors at each round, as a heuristic for better performance. The algorithms are generalized to the asynchronous distributed model. We also introduce a self-stabilizing version of our asynchronous algorithms.
  PubDate: 2023-04-01
Characterizations and Directed Path-Width of Sequence Digraphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Computing the directed path-width of a directed graph is an NP-hard problem. Even for digraphs of maximum semi-degree 3 the problem remains hard. We propose a decomposition of an input digraph G = (V,A) by a number k of sequences with entries from V, such that (u,v) ∈ A if and only if in one of the sequences there is an occurrence of u appearing before an occurrence of v. We present several graph theoretical properties of these digraphs. Among these we give forbidden subdigraphs of digraphs which can be defined by k = 1 sequence, which is a subclass of semicomplete digraphs. Given the decomposition of digraph G, we show an algorithm which computes the directed path-width of G in time \(\mathcal {O}(k\cdot (1+N)^{k})\) , where N denotes the maximum sequence length. This leads to an XP-algorithm w.r.t. k for the directed path-width problem. Our result improves the algorithms of Kitsunai et al. for digraphs of large directed path-width which can be decomposed by a small number of sequences and confirm their conjecture that semicompleteness is a useful restriction when considering digraphs.
  PubDate: 2023-04-01
Polynomially Ambiguous Unary Weighted Automata over Fields
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Every univariate rational series over an algebraically closed field is shown to be realised by some polynomially ambiguous unary weighted automaton. Unary weighted automata over algebraically closed fields thus always admit polynomially ambiguous equivalents. On the other hand, it is shown that this property does not hold over any other field of characteristic zero, generalising a recent observation about unary weighted automata over the field of rational numbers.
  PubDate: 2023-04-01
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear
Grammars
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  PubDate: 2023-02-11
On the Hierarchy of Swarm-automaton for the Number of Agents
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract We have introduced and extended the notion of swarm automaton to analyze the computability using swarm movement represented by multiset rewriting. The two transitions, parallel and sequential, are considered to transform a configuration of multisets at each step in the swarm automaton. In this paper, we focus on the number of agents composing each configuration and analyze the computing power of swarm automaton. From the result of swarm automaton without position information, no swarm automaton has a universal computing power even though we can use infinitely many agents both in parallel rewriting and in sequential rewriting. On the other hand, when we add the information of position for each agent, the swarm automaton has universal computability. We need just four agents in a configuration to simulate any Turing machine.
  PubDate: 2023-02-11
Fixed-Parameter Algorithms for Unsplittable Flow Cover
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Höhn et al. ICALP 2018). In this paper we study fixed-parameter algorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of \(f(k)\cdot n^{O_{\epsilon }(1)}\) that outputs a solution with at most (1 + ðœ–)k tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + ðœ– in the cost of the selected tasks.
  PubDate: 2023-02-01
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract The computational complexity of the VertexCover problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice.
  PubDate: 2023-02-01
Observation and Distinction: Representing Information in Infinite Games
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata. The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.
  PubDate: 2023-02-01
Typical Sequences Revisited — Computing Width Parameters of Graphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in polynomial time.
  PubDate: 2023-02-01
Decidability and Periodicity of Low Complexity Tilings
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract In this paper we study colorings (or tilings) of the two-dimensional grid \({\mathbb {Z}}^{2}\) . A coloring is said to be valid with respect to a set P of n × m rectangular patterns if all n × m sub-patterns of the coloring are in P. A coloring c is said to be of low complexity with respect to a rectangle if there exist \(m,n\in \mathbb {N}\) and a set P of n × m rectangular patterns such that c is valid with respect to P and P ≤ nm. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. If Nivat’s conjecture is true, all valid colorings with respect to P such that P ≤ mn must be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle. After that, we prove that the nm bound is multiplicatively optimal for the decidability of the domino problem, as for all ε > 0 it is undecidable to determine if there exists a valid coloring for a given \(m,n\in \mathbb {N}\) and set of rectangular patterns P of size n × m such that P ≤ (1 + ε)nm. We prove a slightly better bound in the case where m = n, as well as constructing aperiodic SFTs of pretty low complexity. This paper is an extended version of a paper published in STACS 2020 (Kari and Moutot 12).
  PubDate: 2023-02-01
An Automaton Group with PSPACE-Complete Word Problem
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem and acts over a binary alphabet. Thus, it is optimal in terms of the alphabet size. Our construction directly simulates the computation of a Turing machine in an automaton group and, therefore, seems to be quite versatile. It combines two ideas: the first one is a construction used by D’Angeli, Rodaro and the first author to obtain an inverse automaton semigroup with a PSPACE-complete word problem and the second one is to utilize a construction used by Barrington to simulate Boolean circuits of bounded degree and logarithmic depth in the group of even permutations over five elements.
  PubDate: 2023-02-01
Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance \((D^{\prime },k^{\prime })\) of Arc Disjoint Cycle Packing, such that \(k^{\prime }\leq k\) and the size of \(D^{\prime }\) is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by \({\mathcal D}_{\alpha }\) , contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments.
  PubDate: 2023-01-26
Preface of the Special Issue Dedicated to Selected Papers from CSR 2020
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  PubDate: 2023-01-11
  DOI: 10.1007/s00224-022-10115-7
Preface of STACS 2020 Special Issue
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  PubDate: 2023-01-07
  DOI: 10.1007/s00224-022-10116-6
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract For a size parameter \(s:\mathbb {N}\to \mathbb {N}\) , the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}n →{0,1} (represented by a string of length N := 2n) is at most a threshold s(n). A recent line of work exhibited “hardness magnification” phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ1 > 0, if \(\text {MCSP}[2^{\mu _{1}\cdot n}]\) cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N1.01, then P≠NP. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: (1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute \(\text {MCSP}[2^{\mu _{2}\cdot n}]\) in time N1.99, for some constant μ2 > μ1. (2) A non-deterministic (or parity) branching program of size \(o(N^{1.5}/\log N)\) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. (3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least \(N^{1.5-o\left (1\right )}\) . These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola, Electron. Colloq. Comput. Complexity (ECCC) 26, 51, 2019). En route, we obtain several related results: (1) There exists a (local) hitting set generator with seed length \(\widetilde {O}(\sqrt {N})\) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. (2) Any read-once co-non-deterministic branching program computing MCSP must have size at least \(2^{\widetilde {\Omega }(N)}\) .
  PubDate: 2022-12-27
  DOI: 10.1007/s00224-022-10113-9
On Embeddability of Unit Disk Graphs Onto Straight Lines
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e. unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be \(\exists \mathbb {R}\) -complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. Following the same line, we also describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either x-axis or y-axis. Adjusting the reduction, we also show that this problem is NP-complete when the given lines are only parallel to x-axis. We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.
  PubDate: 2022-12-17
  DOI: 10.1007/s00224-022-10110-y
Complexity Limitations on One-turn Quantum Refereed Games
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: This paper studies complexity theoretic aspects of quantum refereed games, which are abstract games between two competing players that send quantum states to a referee, who performs an efficiently implementable joint measurement on the two states to determine which of the player wins. The complexity class QRG(1) contains those decision problems for which one of the players can always win with high probability on yes-instances and the other player can always win with high probability on no-instances, regardless of the opposing player’s strategy. This class trivially contains QMA ∪co-QMA and is known to be contained in PSPACE. We prove stronger containments on two restricted variants of this class. Specifically, if one of the players is limited to sending a classical (probabilistic) state rather than a quantum state, the resulting complexity class CQRG(1) is contained in ∃⋅PP (the nondeterministic polynomial-time operator applied to PP); while if both players send quantum states but the referee is forced to measure one of the states first, and incorporates the classical outcome of this measurement into a measurement of the second state, the resulting class MQRG(1) is contained in P ⋅PP (the unbounded-error probabilistic polynomial-time operator applied to PP).
  PubDate: 2022-12-10
  DOI: 10.1007/s00224-022-10105-9
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding
the Reach of #SAT Algorithms
- Free pre-print version: Loading...
  Rate this result: What is this?
  
  Please help us test our new pre-print finding feature by giving the pre-print link a rating.
  A 5 star rating indicates the linked pre-print has the exact same content as the published article.
  
  Abstract: Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in \(\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]\) and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes \(\mathcal { C}\) , by showing that \(\mathcal { C}\) admits non-trivial satisfiability and/or # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial # SAT algorithm for a circuit class \({\mathcal C}\) . Say that a symmetric Boolean function f(x1,…,xn) is sparse if it outputs 1 on O(1) values of \({\sum }_{i} x_{i}\) . We show that for every sparse f, and for all “typical” \(\mathcal { C}\) , faster # SAT algorithms for \(\mathcal { C}\) circuits imply lower bounds against the circuit class \(f \circ \mathcal { C}\) , which may be stronger than \(\mathcal { C}\) itself. In particular: # SAT algorithms for nk-size \(\mathcal { C}\) -circuits running in 2n/nk time (for all k) imply NEXP does not have \((f \circ \mathcal { C})\) -circuits of polynomial size. # SAT algorithms for \(2^{n^{{\varepsilon }}}\) -size \(\mathcal { C}\) -circuits running in \(2^{n-n^{{\varepsilon }}}\) time (for some ε > 0) imply Quasi-NP does not have \((f \circ \mathcal { C})\) -circuits of polynomial size. Applying # SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMAJ ∘ ACC0 ∘ THR circuits of polynomial size, where EMA
  PubDate: 2022-11-04
  DOI: 10.1007/s00224-022-10106-8