Search

The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete a set S of at most k vertices of G such that the resulting graph G - S is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is NP -complete. Moreover, in the NP -completeness cases, cluster-vd cannot be solved in sub-exponential time in the vertex number of the H-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of cluster-vd, the Connected Cluster Vertex Deletion problem (connected cluster-vd), in which the set S has to induce a connected subgraph of G. It turns out that connected cluster-vd admits the same complexity dichotomy for H-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on H-free graphs. [ABSTRACT FROM AUTHOR]

We show that completeness at higher levels of the theory of the reals is a robust notion (under changing the signature and bounding the domain of the quantifiers). This mends recognized gaps in the hierarchy, and leads to stronger completeness results for various computational problems. We exhibit several families of complete problems which can be used for future completeness results in the real hierarchy. As an application we sharpen some results by Bürgisser and Cucker on the complexity of properties of semialgebraic sets, including the Hausdorff distance problem also studied by Jungeblut, Kleist, and Miltzow. [ABSTRACT FROM AUTHOR]

In a hedonic diversity game (HDG) there are two types of agents (red and blue agents) that need to form disjoint coalitions, i.e., subgroups of agents. Each agent's preferences over the coalitions depend on the relative number of agents of the same type in her coalition. In the special case of a dichotomous hedonic diversity game (DHDG) each agent distinguishes between approved and disapproved fractions only. We aim at outcomes that are stable against agents' deviations, and at outcomes that maximize social welfare. In particular, we show that the strict core of a DHDG may be empty even in instances with only three agents, while each HDG with two agents has a non-empty strict core. We also provide several computational complexity results for DHDGs with respect to the number of fractions approved per agent. For instance, we prove that deciding whether a DHDG has a non-empty strict core is NP -complete even when each agent approves of at most three fractions. In addition, we show that deciding whether a DHDG admits a Nash stable outcome is NP -complete even in restricted settings with only two approved fractions per agent—therewith, improving a result in the literature. For the task of maximizing social welfare, we apply approval scores and Borda scores from voting theory. For DHDGs and approval scores, we draw the sharp separation line between polynomially solvable and NP -complete cases with respect to the fixed number of approved fractions per agent. We complement these findings with an NP -completeness result for HDGs under Borda scores. [ABSTRACT FROM AUTHOR]

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Notice that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O (log n) time. Therefore, upper-bounding the numbers used as vertex labels also upper-bounds the space complexity of storing the graph in the database. We show that every n-vertex, m-edge, d-degenerate graph can be made a sum graph by adding at most m isolated vertices to it, such that the largest numbers used as vertex labels grows as O (n 2 d) . This enables us to store the graph using O (m log n) bits of memory. For sparse graphs (graphs with O (n) edges), this matches the trivial lower bound of Ω (n log n) . As planar graphs and forests have constant degeneracy, our result implies an upper bound of O (n 2) on their label numbers. The previously best known upper bound on the numbers needed for labelling general graphs with the minimum number of isolated vertices was O (4 n) , due to Kratochvíl, Miller & Nguyen (2001). Furthermore, their proof was existential, whereas our labelling can be constructed in polynomial time. [ABSTRACT FROM AUTHOR]

A classic result of Paul, Pippenger, Szemerédi and Trotter states that DTIME (n) ⫋ NTIME (n) . The natural question then arises: could the inclusion DTIME (t (n)) ⊆ NTIME (n) hold for some superlinear time-constructible function t(n)? If such a function t(n) does exist, then there also exist effective nondeterministic guessing strategies to speed up deterministic computations. In this work, we prove limitations on the effectiveness of nondeterministic guessing to speed up deterministic computations by showing that the existence of effective nondeterministic guessing strategies would have unlikely consequences. In particular, we show that if a subpolynomial amount of nondeterministic guessing could be used to speed up deterministic computation by a polynomial factor, then P ⫋ NTIME (n) . Furthermore, even achieving a logarithmic speedup at the cost of making every step nondeterministic would show that SAT ∈NTIME(n) under appropriate encodings. Of possibly independent interest, under such encodings we also show that SAT can be decided in O(nlogn) steps on a nondeterministic multitape Turing machine, improving on the well-known O(n(logn)c) bound for some constant but undetermined exponent c ≥ 1. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the complexity of a number of computational problems defined on a synchronous boolean finite dynamical system, where update functions are chosen from a template set of exclusive-or and its negation. We first show that the reachability and path-intersection problems are solvable in logarithmic space-uniform AC1 if the objects execute permutations, while the reachability problem is known to be in P and the path-intersection problem to be in UP in general. We also explore the case where the reachability or intersection are tested on a subset of objects, and show that this hardens complexity of the problems: both problems become NP-complete, and even π 2 p -complete if we further require universality of the intersection. We next consider the exact cycle length problem, that is, determining whether there exists an initial configuration that yields a cycle in the configuration space having exactly a given length, and show that this problem is NP-complete. Lastly, we consider the t-predecessor and t-Garden of Eden problem, and prove that these are solvable in polynomial time even if the value of t is also given in binary as part of instance, and the two problems are in logarithmic space-uniform NC2 if the value of t is given in unary as part of instance. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism ϕ : A + → B + such that ϕ(α) is a factor of w. We discuss unavoidability in the milieu of various types of complexity. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that can avoid them. We then discuss the relative density of unavoidable words. Subsequently, we investigate computational aspects of unavoidable words, focusing on the computational complexity of determining whether a word is unavoidable. This culminates in a proof that this problem is NP-complete. [ABSTRACT FROM AUTHOR]

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations: There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity cannot be replaced by a polynomial number of queries. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it impossible to simulate by a nonuniform reduction with fixed polynomial advice. There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing. We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, every set that is complete for NP under nonuniform truth-table reductions is also uniformly truth-table complete. [ABSTRACT FROM AUTHOR]

We study the computational complexity of decision problems about Nash equilibria in m-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes, ∃ ℝ -complete, when m ≥ 3. We show that, unless they turn into trivial problems, they are ∃ ℝ -hard even for 3-player zero-sum games. We also obtain new results about several other decision problems. We show that when m ≥ 3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are ∃ ℝ -complete. The latter result rectifies a previous claim of NP-completeness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is ∃ ℝ -hard, answering a question of Bilò and Mavronicolas, and address also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results also hold for 3-player zero-sum games. Our proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric m-player game has a non-symmetric Nash equilibrium is ∃ ℝ -complete when m ≥ 3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod. [ABSTRACT FROM AUTHOR]

We prove a complexity classification for Holant problems defined by an arbitrary set of complex-valued symmetric constraint functions on Boolean variables. This is to specifically answer the question: Is the Fisher-Kasteleyn-Temperley (FKT) algorithm under a holographic transformation (Valiant, SIAM J. Comput. 37(5), 1565–1594 2008) a universal strategy to obtain polynomial-time algorithms for problems over planar graphs that are intractable on general graphs? There are problems that are #P-hard on general graphs but polynomial-time solvable on planar graphs. For spin systems (Kowalczyk 2010) and counting constraint satisfaction problems (#CSP) (Guo and Williams, J. Comput. Syst. Sci. 107, 1–27 2020), a recurring theme has emerged that a holographic reduction to FKT precisely captures these problems. Surprisingly, for Holant, we discover new planar tractable problems that are not expressible by a holographic reduction to FKT. In particular, a straightforward formulation of a dichotomy for planar Holant problems along the above recurring theme is false. A dichotomy theorem for #CSPd, which denotes #CSP where every variable appears a multiple of d times, has been an important tool in previous work. However the proof for the #CSPd dichotomy violates planarity, and it does not generalize to the planar case easily. In fact, due to our newly discovered tractable problems, the putative form of a planar #CSPd dichotomy is false when d ≥ 5. Nevertheless, we prove a dichotomy for planar #CSP2. In this case, the putative form of the dichotomy is true. (This is presented in Part II of the paper.) We manage to prove the planar Holant dichotomy relying only on this planar #CSP2 dichotomy, without resorting to a more general planar #CSPd dichotomy for d ≥ 3. A special case of the new polynomial-time computable problems is counting perfect matchings (#PM) over k-uniform hypergraphs when the incidence graph is planar and k ≥ 5. The same problem is #P-hard when k = 3 or k = 4, which is also a consequence of our dichotomy. When k = 2, it becomes #PM over planar graphs and is tractable again. More generally, over hypergraphs with specified hyperedge sizes and the same planarity assumption, #PM is polynomial-time computable if the greatest common divisor (gcd) of all hyperedge sizes is at least 5. It is worth noting that it is the gcd, and not a bound on hyperedge sizes, that is the criterion for tractability. [ABSTRACT FROM AUTHOR]

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r ≥ 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k ≤ 2 and k ≥ 3. For the latter case it is known that for all x ≥ 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k ≤ 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph. [ABSTRACT FROM AUTHOR]

We discuss a game theoretic variant of the subset sum problem, in which two players compete for a common resource represented by a knapsack. Each player owns a private set of items, players pack items alternately, and each player either wants to maximize the total weight of his own items packed into the knapsack or to minimize the total weight of the items of the other player. We show that finding the best packing strategy against a hostile or a selfish adversary is PSPACE-complete, and that against these adversaries the optimal reachable item weight for a player cannot be approximated within any constant factor (unless P=NP). The game becomes easier when the adversary is short-sighted and plays greedily: finding the best packing strategy against a greedy adversary is NP-complete in the weak sense. This variant forms one of the rare examples of pseudo-polynomially solvable problems that have a PTAS, but do not allow an FPTAS (unless P=NP). [ABSTRACT FROM AUTHOR]

Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph G can be defined with help of a chip firing game on G. The stable divisorial gonality of G is the minimum divisorial gonality over all subdivisions of edges of G. In this paper we prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer k belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard by Gijswijt et al., we obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, we have that the total number of subdivisions needed for minimum stable divisorial gonality of a graph with m edges is bounded by mO(mn). [ABSTRACT FROM AUTHOR]

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: PSpace-complete in general, and NLogSpace-complete for predicates of bounded arity. These complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest. [ABSTRACT FROM AUTHOR]

The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at most k times in any path from the root to a sink. In a preliminary version of this paper, we provide a satisfiability algorithm for syntactic read-k-times branching programs with n variables and m edges that runs in time O poly (n , m k 2 ) ⋅ 2 (1 − 4 − k − 1) n . In this paper, we improve the bounds for k = 2. More precisely, we show that the satisfiability of syntactic read-twice branching programs can be solved in time O poly (n , m) ⋅ 2 5 n / 6 . Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993]. [ABSTRACT FROM AUTHOR]

We strengthen a result by Laskar and Lyle (Discrete Appl. Math. 157, 330–338 2009) by proving that it is NP-complete to decide whether a bipartite planar graph can be partitioned into three independent dominating sets. In contrast, we show that this is always possible for every maximal outerplanar graph with at least three vertices. Moreover, we extend their previous result by proving that deciding whether a bipartite graph can be partitioned into k independent dominating sets is NP-complete for every k ≥ 3. We also strengthen a result by Henning et al. (Discrete Math. 309(23), 6451–6458 2009) by showing that it is NP-complete to determine if a graph has two disjoint independent dominating sets, even when the problem is restricted to triangle-free planar graphs. Finally, for every k ≥ 3, we show that there is some constant t depending only on k such that deciding whether a k-regular graph can be partitioned into t independent dominating sets is NP-complete. We conclude by deriving moderately exponential-time algorithms for the problem. [ABSTRACT FROM AUTHOR]

In Peer-to-Peer (P2P) network systems, content (object) delivery between nodes is often required. One way to study such a distributed system is by defining games, which involve selfish nodes that make strategic choices on replicating content in their local limited memory (cache) or accessing content from other nodes for a cost. These Selfish Replication games have been introduced in Chun et al. (2004) for nodes that do not have any capacity limits, leaving the capacitated problem, i.e. Capacitated Selfish Replication (CSR) games, open. In this work, we first form the model of the CSR games, for which we perform a Nash equilibria analysis. In particular, we focus on hierarchical networks, given their extensive use to model communication costs of content delivery in P2P systems. We present an exact polynomial-time algorithm for any hierarchical network, under two constraints on the utility functions: 1) "Nearer is better", i.e. the closest the content is to the node the less its access cost is, and 2) "Independence of irrelevant alternatives", i.e. aggregation of individual node preferences. This generalization represents a vast class of utilities and more interestingly allows each of the nodes to have simultaneously completely different functional forms of utility functions. In this general framework, we present CSR games results on arbitrary networks and outline the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. Moreover, we prove that the problem of equilibria existence becomes NP-hard for general CSR games. By adding some constraints in the number of objects and their preferences, we show that the equilibrium can be found in polynomial time. Finally, we introduce the fractional version of CSR games (F-CSR) to represent content distribution. We prove that equilibrium exists for every F-CSR game, but it is PPAD-complete. [ABSTRACT FROM AUTHOR]

We study Parallel Task Scheduling Pm|sizej|Cmax with a constant number of machines. This problem is known to be strongly NP-complete for each m ≥ 5, while it is solvable in pseudo-polynomial time for each m ≤ 3. We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for m = 4. As a second result, we improve the lower bound of 12 11 for approximating pseudo-polynomial Strip Packing to 5 4 . Since the best known approximation algorithm for this problem has a ratio of 5 4 + ε , this result almost closes the gap between approximation ratio and inapproximability result. Both results are proved by a reduction from the strongly NP-complete problem 3-Partition. [ABSTRACT FROM AUTHOR]

We show that for several solution concepts for finite n-player games, where n ≥ 3, the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games of perfect recall. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where n ≥ 3, is also equivalent to the decision problem for the existential theory of the reals. Our results thus improve previous results of NP-hardness as well as Sqrt-Sum-hardness of the decision problems to completeness for ∃ ℝ , the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and Štefankovič giving ∃ ℝ -completeness for the problem of deciding existence of a probability constrained Nash equilibrium. [ABSTRACT FROM AUTHOR]

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from "classical" algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10). [ABSTRACT FROM AUTHOR]

We study the class of binary coded versions of unary languages that can be accepted by alternating machines with loglog n space. We show that there exists a binary PSpace-complete language ℒ such that the unary coded version of ℒ is in ASpace(loglog n). Consequently, the standard translation between unary languages accepted with loglog n space and binary languages accepted with log n space works for alternating machines if and only ifP = PSpace. In general, if a binary language is accepted deterministically in 2n⋅nO(1) time and, simultaneously, in nO(1) space—which covers many PSpace-complete problems—then its unary coded version is accepted by an alternating Turing machine using an initially delimited worktape of size loglog n. This unexpected power follows from the fact that, with an auxiliary worktape of size O(loglog n) on a unary input 1n, an alternating machine can simulate a stack with log n bits, representing the contents of the stack by its input head position. The standard push/pop operations on the stack are implemented by moving the head along the input. [ABSTRACT FROM AUTHOR]

We study the complexity of motivating time-inconsistent agents to complete long term projects in a graph-based planning model proposed by Kleinberg and Oren (2014). Given a task graph G with n nodes, our objective is to guide an agent towards a target node t under certain budget constraints. The crux is that the agent may change its strategy over time due to its present-bias. We consider two strategies to guide the agent. First, a single reward is placed at t and arbitrary edges can be removed from G. Secondly, rewards can be placed at arbitrary nodes of G but no edges must be deleted. In both cases we show that it is NP-complete to decide if a given budget is sufficient to keep the agent motivated. For the first setting, we give complementing upper and lower bounds on the approximability of the minimum required budget. In particular, we devise a (1 + n) -approximation algorithm and prove NP-hardness for ratios greater than n / 3 . We also argue that the second setting does not permit any efficient approximation unless P = NP. [ABSTRACT FROM AUTHOR]

Cost register automata (CRAs) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring (ℕ ∪ { ∞ } , min , +) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P -complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC 1 when the semiring is (ℤ , + , ×) or (Γ ∗ ∪ { ⊥ } , max , concat) . This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1. [ABSTRACT FROM AUTHOR]

Weighted voting games (WVGs) are a class of cooperative games that capture settings of group decision making in various domains, such as parliaments or committees. Earlier work has revealed that the effective decision making power, or influence of agents in WVGs is not necessarily proportional to their weight. This gave rise to measures of influence for WVGs. However, recent work in the algorithmic game theory community have shown that computing agent voting power is computationally intractable. In an effort to characterize WVG instances for which polynomial-time computation of voting power is possible, several classes of WVGs have been proposed and analyzed in the literature. One of the most prominent of these are super increasing weight sequences. Recent papers show that when agent weights are super-increasing, it is possible to compute the agents' voting power (as measured by the Shapley value) in polynomial-time. We provide the first set of explicit closed-form formulas for the Shapley value for super-increasing sequences. We bound the effects of changes to the quota, and relate the behavior of voting power to a novel function. This set of results constitutes a complete characterization of the Shapley value in weighted voting games, and answers a number of open questions presented in previous work. [ABSTRACT FROM AUTHOR]

We investigate the problem of equilibrium computation for "large" n-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most 1n. We study algorithms having query access to the game's payoff function, aiming to find ε-Nash equilibria. We seek algorithms that obtain ε as small as possible, in time polynomial in n. Our main result is a randomised algorithm that achieves ε approaching 18 for 2-strategy games in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. O(log n) rounds/queries are required. We also show how to obtain a slight improvement over 18, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters. [ABSTRACT FROM AUTHOR]

Let P be a set of points in the plane. The goal is to place two unit disks in the plane such that the number of points from P covered by the disks is maximized. In addition, the distance between the centers of the two disks should not exceed a specified constant Rc ≥ 0. We propose two algorithms to solve this problem. The first algorithm is a simple exhaustive algorithm which runs in O(n4) time. We then improve this algorithm by a constructing connectivity region and building a segment tree to compute two optimal disks. The resulting algorithm has O(n3logn) time complexity. [ABSTRACT FROM AUTHOR]

In this paper, we study the advice complexity of the online bin packing problem. In this well-studied setting, the online algorithm is supplemented with some additional information concerning the input. We improve upon both known upper and lower bounds of online algorithms for this problem. On the positive side, we first provide a relatively simple algorithm that achieves a competitive ratio arbitrarily close to 1.5, using constant-size advice. Our result implies that 16 bits of advice suffice to obtain a competitive ratio better than any online algorithm without advice, thus improving the previously known bound of O(log(n)) bits required to attain this performance. In addition, we introduce a more complex algorithm that still requires only constant-size advice, and has a competitive ratio arbitrarily close to 1.47012. This is the currently best performance of any online bin packing algorithm with sublinear advice. On the negative side, we extend a construction due to Boyar et al. (Algorithmica 74(1), 507-527 2016) so as to show that no online algorithm with sub-linear advice can be 7/6-competitive, improving on the lower bound of 9/8 from Boyar et al. [ABSTRACT FROM AUTHOR]

A minimal deterministic finite automaton (DFA) is uniformly minimal if it always remains minimal when the final state set is replaced by a non-empty proper subset of the state set. We prove that a permutation DFA is uniformly minimal if and only if its transition monoid is a primitive group. We use this to study Boolean operations on group languages, which are recognized by direct products of permutation DFAs. A direct product cannot be uniformly minimal, except in the trivial case where one of the DFAs in the product is a one-state DFA. However, non-trivial direct products can satisfy a weaker condition we call uniform Boolean minimality, where only final state sets used to recognize Boolean operations are considered. We give sufficient conditions for a direct product of two DFAs to be uniformly Boolean minimal, which in turn gives sufficient conditions for pairs of group languages to have maximal state complexity under all binary Boolean operations (“maximal Boolean complexity”). In the case of permutation DFAs with one final state, we give necessary and sufficient conditions for pairs of group languages to have maximal Boolean complexity. Our results demonstrate a connection between primitive groups and automata with strong minimality properties. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of voter control problems in κ-peaked elections, where κ is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for Condorcet, Maximin and Copelandα. It is known that in general elections all these problems are NP-hard, except for the destructive control by adding/deleting votes for Condorcet which is polynomial-time solvable. We strengthen these results by showing that, when restricted to κ-peaked elections where κ = 3,4, the above NP-hard problems not only remain NP-hard but also are W[1]-hard with respect to the number of added/deleted votes. [ABSTRACT FROM AUTHOR]

Recently, the first online complexity class, AOC, was introduced. The class consists of many online problems where each request must be either accepted or rejected, and the aim is to either minimize or maximize the number of accepted requests, while maintaining a feasible solution. All AOC-complete problems (including Independent Set, Vertex Cover, Dominating Set, and Set Cover) have essentially the same advice complexity. In this paper, we study weighted versions of problems in AOC, i.e., each request comes with a weight and the aim is to either minimize or maximize the total weight of the accepted requests. In contrast to the unweighted versions, we show that there is a significant difference in the advice complexity of complete minimization and maximization problems. We also show that our algorithmic techniques for dealing with weighted requests can be extended to work for non-complete AOC problems such as Matching in the edge arrival model (giving better results than what follow from the general AOC results) and even non- AOC problems such as scheduling. [ABSTRACT FROM AUTHOR]

We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier NP-hardness results by Håstad (J. Algorithm. 11(4), 644-654 1990). The hardness proof also implies an algebraic universality result. [ABSTRACT FROM AUTHOR]

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and n+nmax{1,T−1}(δ−1)±Θ(δ) time units otherwise, where δ is the maximum time between two successive appearances of an edge. [ABSTRACT FROM AUTHOR]

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theories of typed monoids and of rational series are used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh automata languages in NC1. Affine Parikh automata, where each transition applies an affine transformation on the registers, are also considered. Relying on these characterizations, the landscape of relationships and closure properties of the classes at hand is completed, in particular over unary languages. [ABSTRACT FROM AUTHOR]

We study the complexity of graph problems succinctly encoded by bounded depth circuits and the existence of upward translation theorems for these models. While almost all succinct encodings have an upward translation theorem for some type of reduction, we prove that such theorems for CNF- and DNF-encoded graphs and for the most studied reductions do not exist. In contrast, we show that there are upward translation theorems for AC0 circuits of depth at least 3. This implies that the complexity of the succinct versions of problems complete for NP (under quantifier-free reductions), encoded by such circuits, have an exponential blow-up. We adapt these results to problems on explicitly given graphs with the same structural properties as graphs encoded by bounded depth circuits. We define a graph class hierarchy Ik which consists of at most k alternating unions and intersections of edge-sets in I0, a class which only consists of single bicliques. We show that the complexity of every NP-complete problem (under quantifier-free reductions) collapses to the second level: on graphs in I2 the problem is already NP-complete. Finally, we show that by restricting I2 to use only sub-logarithmic many intersections we get graphs for which Dominating Set is not NP-complete unless the Exponential Time Hypothesis is false. In contrast, a degree of O(log n) is enough for NP-completeness. Therefore, Dominating Set on I2 graphs with intersection-degree O(logδ(n)) has either a spontaneous transition from P (for all δ < 1) to NP-complete (for δ = 1), or is NP-intermediate on the restricted graph class (for some δ < 1). [ABSTRACT FROM AUTHOR]

In this paper, we propose a reduction of the minimization problem for a bottom-up deterministic tree automaton (DFTA), making the latter a minimization of a string deterministic finite automaton (DFA). To achieve this purpose, we proceed first by the transformation of the tree automaton into a particular string automaton, followed by minimizing this string automaton. In addition, we show that for our transformation, the minimization of the resulting string automaton coincides with the minimization of the original tree automaton. Finally, we discuss the complexity of our proposal for different types of tree automata, namely: standard, acyclic, incremental, and incrementally constructed tree automata. [ABSTRACT FROM AUTHOR]

The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity n of languages in that class. We prove that nn−1, nn−1 + n − 1, and nn−2 + (n − 2)2n−2 + 1 are tight upper bounds on the syntactic complexities of right ideals and prefix-closed languages, left ideals and suffix-closed languages, and two-sided ideals and factor-closed languages, respectively. Moreover, we show that the transition semigroups meeting the upper bounds for all three types of ideals are unique, and the numbers of generators (4, 5, and 6, respectively) cannot be reduced. [ABSTRACT FROM AUTHOR]

Parametric timed automata (PTA) have been introduced by Alur, Henzinger, and Vardi as an extension of timed automata in which clocks can be compared against parameters. The reachability problem asks for the existence of an assignment of the parameters to the non-negative integers such that reachability holds in the underlying timed automaton. The reachability problem for PTA is long known to be undecidable, already over three parametric clocks. A few years ago, Bundala and Ouaknine proved that for PTA over two parametric clocks and one parameter the reachability problem is decidable and also showed a lower bound for the complexity class PSPACENEXP. Our main result is that the reachability problem for two-parametric timed automata with one parameter is EXPSPACE-complete. Our contribution is two-fold. For the EXPSPACE lower bound, inspired by [13, 14], we make use of deep results from complexity theory, namely a serializability characterization of EXPSPACE (in turn based on Barrington’s Theorem) and a logspace translation of numbers in Chinese remainder representation to binary representation due to Chiu, Davida, and Litow. It is shown that with small PTA over two parametric clocks and one parameter one can simulate serializability computations. For the EXPSPACE upper bound, we first give a careful exponential time reduction from PTA over two parametric clocks and one parameter to a (slight subclass of) parametric one-counter automata over one parameter based on a minor adjustment of a construction due to Bundala and Ouaknine. For solving the reachability problem for parametric one-counter automata with one parameter, we provide a series of techniques to partition a fictitious run into several carefully chosen subruns that allow us to prove that it is sufficient to consider a parameter value of exponential magnitude only. This allows us to show a doubly-exponential upper bound on the value of the only parameter of a PTA over two parametric clocks and one parameter. We hope that extensions of our techniques lead to finally establishing decidability of the long-standing open problem of reachability in parametric timed automata with two parametric clocks (and arbitrarily many parameters) and, if decidability holds, determinining its precise computational complexity. [ABSTRACT FROM AUTHOR]

A semilinear relation S⊆ℚn is max-closed if it is preserved by taking the componentwise maximum. The constraint satisfaction problem for max-closed semilinear constraints is at least as hard as determining the winner in Mean Payoff Games, a notorious problem of open computational complexity. Mean Payoff Games are known to be in NP ∩ co− NP, which is not known for max-closed semilinear constraints. Semilinear relations that are max-closed and additionally closed under translations have been called tropically convex in the literature. One of our main results is a new duality for open tropically convex relations, which puts the CSP for tropically convex semilinear constraints in general into NP ∩ co− NP. This extends the corresponding complexity result for scheduling under and-or precedence constraints, or equivalently the max-atoms problem. To this end, we present a characterization of max-closed semilinear relations in terms of syntactically restricted first-order logic, and another characterization in terms of a finite set of relations L that allow primitive positive definitions of all other relations in the class. We also present a subclass of max-closed constraints where the CSP is in P; this class generalizes the class of max-closed constraints over finite domains, and the feasibility problem for max-closed linear inequalities. Finally, we show that the class of max-closed semilinear constraints is maximal in the sense that as soon as a single relation that is not max-closed is added to L, the CSP becomes NP-hard. [ABSTRACT FROM AUTHOR]

We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [ n] and a property $\mathcal {P}$ , the goal is to distinguish between D ∈ $\mathcal {P}$ and ℓ( D, $\mathcal {P}$ ) > ε. We develop a general algorithm for this question, which applies to a large range of 'shape-constrained' properties, including monotone, log-concave, t-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions. [ABSTRACT FROM AUTHOR]

Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation. [ABSTRACT FROM AUTHOR]

We demonstrate that the Weihrauch lattice can be used to classify the uniform computational content of computability-theoretic properties as well as the computational content of theorems in one common setting. The properties that we study include diagonal non-computability, hyperimmunity, complete consistent extensions of Peano arithmetic, 1-genericity, Martin-Löf randomness, and cohesiveness. The theorems that we include in our case study are the low basis theorem of Jockusch and Soare, the Kleene-Post theorem, and Friedberg's jump inversion theorem. It turns out that all the aforementioned properties and many theorems in computability theory, including all theorems that claim the existence of some Turing degree, have very little uniform computational content: they are located outside of the upper cone of binary choice (also known as LLPO); we call problems with this property indiscriminative. Since practically all theorems from classical analysis whose computational content has been classified are discriminative, our observation could yield an explanation for why theorems and results in computability theory typically have very few direct consequences in other disciplines such as analysis. A notable exception in our case study is the low basis theorem which is discriminative. This is perhaps why it is considered to be one of the most applicable theorems in computability theory. In some cases a bridge between the indiscriminative world and the discriminative world of classical mathematics can be established via a suitable residual operation and we demonstrate this in the case of the cohesiveness problem and the problem of consistent complete extensions of Peano arithmetic. Both turn out to be the quotient of two discriminative problems. [ABSTRACT FROM AUTHOR]

The definition of conditional probability in the case of continuous distributions (for almost all conditions) was an important step in the development of mathematical theory of probabilities. Can we define this notion in algorithmic probability theory for individual random conditions? Can we define randomness with respect to the conditional probability distributions? Can van Lambalgen's theorem (relating randomness of a pair and its elements) be generalized to conditional probabilities? We discuss the developments in this direction. We present almost no new results trying to put known results into perspective and explain their proofs in a more intuitive way. We assume that the reader is familiar with basic notions of measure theory and algorithmic randomness (see, e.g., Shen et al. ??2013 or Shen ??2015 for a short introduction). [ABSTRACT FROM AUTHOR]

We consider the typical asymptotic behaviour of cellular automata of higher dimension (≥2). That is, we take an initial configuration at random according to a Bernoulli (i.i.d) probability measure, iterate some cellular automaton, and consider the (set of) limit probability measure(s) as t → ∞. In this paper, we prove that limit measures that can be reached by higher-dimensional cellular automata are completely characterised by computability conditions, as in the one-dimensional case. This implies that cellular automata have the same variety and complexity of typical asymptotic behaviours as Turing machines, and that any nontrivial property in this regard is undecidable (Rice-type theorem). These results extend to connected sets of limit measures and Cesàro mean convergence. The main tool is the implementation of arbitrary computation in the time evolution of a cellular automata in such a way that it emerges and self-organises from a random configuration. [ABSTRACT FROM AUTHOR]

An a priori semimeasure (also known as 'algorithmic probability' or 'the Solomonoff prior' in the context of inductive inference) is defined as the transformation, by a given universal monotone Turing machine, of the uniform measure on the infinite strings. It is shown in this paper that the class of a priori semimeasures can equivalently be defined as the class of transformations, by all compatible universal monotone Turing machines, of any continuous computable measure in place of the uniform measure. Some consideration is given to possible implications for the association of algorithmic probability with certain foundational principles of statistics. [ABSTRACT FROM AUTHOR]

The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice complexity, we define the first online complexity class, AOC. The class includes independent set, vertex cover, dominating set, and several others as complete problems. AOC-complete problems are hard, since a single wrong answer by the online algorithm can have devastating consequences. For each of these problems, we show that $\log \left (1+(c-1)^{c-1}/c^{c}\right )n={\Theta } (n/c)$ bits of advice are necessary and sufficient (up to an additive term of $O(\log n)$ ) to achieve a competitive ratio of c. The results are obtained by introducing a new string guessing problem related to those of Emek et al. (Theor. Comput. Sci. 412(24), 2642-2656 2011) and Böckenhauer et al. (Theor. Comput. Sci. 554, 95-108 2014). It turns out that this gives a powerful but easy-to-use method for providing both upper and lower bounds on the advice complexity of an entire class of online problems, the AOC-complete problems. Previous results of Halldórsson et al. (Theor. Comput. Sci. 289(2), 953-962 2002) on online independent set, in a related model, imply that the advice complexity of the problem is Θ( n/ c). Our results improve on this by providing an exact formula for the higher-order term. For online disjoint path allocation, Böckenhauer et al. (ISAAC 2009) gave a lower bound of Ω( n/ c) and an upper bound of $O((n\log c)/c)$ on the advice complexity. We improve on the upper bound by a factor of $\log c$ . For the remaining problems, no bounds on their advice complexity were previously known. [ABSTRACT FROM AUTHOR]

Generalizing the notion of automatic complexity of individual words due to Shallit and Wang, we define the automatic complexity A( E) of an equivalence relation E on a finite set S of words. We prove that the problem of determining whether A( E) equals the number | E| of equivalence classes of E is -complete. The problem of determining whether A( E) = | E| + k for a fixed k ≥ 1 is complete for the second level of the Boolean hierarchy for , i.e., -complete. Let L be the language consisting of all words of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of L by showing that they can be co-context-free but not context-free, i.e., L is -immune, but not -immune. We show that for each ε > 0, L ∉ , where L is the set of all words whose deterministic automatic complexity A( x) satisfies A( x) ≥ | x|. [ABSTRACT FROM AUTHOR]

Semiautomatic structures generalise automatic structures in the sense that for some of the relations and functions in the structure one only requires the derived relations and functions are automatic when all but one input are filled with constants. One can also permit that this applies to equality in the structure so that only the sets of representatives equal to a given element of the structure are regular while equality itself is not an automatic relation on the domain of representatives. It is shown that one can find semiautomatic representations for the field of rationals and also for finite algebraic field extensions of it. Furthermore, one can show that infinite algebraic extensions of finite fields have semiautomatic representations in which the addition and equality are both automatic. Further prominent examples of semiautomatic structures are term algebras, any relational structure over a countable domain with a countable signature and any permutation algebra with a countable domain. Furthermore, examples of structures which fail to be semiautomatic are provided. [ABSTRACT FROM AUTHOR]

For two integers r, ℓ ≥ 0, a graph G = ( V, E) is an ( r, ℓ)-graph if V can be partitioned into r independent sets and ℓ cliques. In the parameterized ( r, ℓ)- Vertex Deletion problem, given a graph G and an integer k, one has to decide whether at most k vertices can be removed from G to obtain an ( r, ℓ)-graph. This problem is NP-hard if r + ℓ ≥ 1 and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of ( r, ℓ)- Vertex Deletion was known for all values of ( r, ℓ) except for (2,1), (1,2), and (2,2). We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of k. We consider as well the version of ( r, ℓ)- Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem. [ABSTRACT FROM AUTHOR]

The Secluded Path problem models a situation where sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure cost, which is the total cost of vertices in its closed neighborhood. The task is to select a secluded path, i.e., a path with a small exposure cost. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure cost of the tree is minimized. In this paper we present a systematic study of the parameterized complexity of Secluded Steiner Tree. In particular, we establish the tractability of Secluded Path being parameterized by 'above guarantee' value, which in this case is the length of a shortest path between vertices. We also show how to extend this result for Secluded Steiner Tree, in this case we parameterize above the size of an optimal Steiner tree and the number of terminals. We also consider various parameterization of the problems such as by the treewidth, the size of a vertex cover, feedback vertex set, or the maximum vertex degree and establish kernelization complexity of the problem subject to different choices of parameters. [ABSTRACT FROM AUTHOR]