Search

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.

The CONSTRAINED BIPARTITE VERTEX COVER problem asks, for a bipartite graph G with partite sets A and B, and integers kA and kB, whether there is a vertex cover for G containing at most kA vertices from A and kB vertices from B. The problem has an easy kernel with 2ka · kb edges and 4kA · kb vertices, based on the fact that every vertex in A of degree more than kB has to be included in the solution, together with every vertex in B of degree more than kA. We show that the number of vertices and edges in this kernel are asymptotically essentially optimal in terms of the product kA· kB. We prove that if there is a polynomial-time algorithm that reduces any instance (G,A,B, kA, kB) of CONSTRAINED BIPARTITE VERTEX COVER to an equivalent instance (G', A', B', k'A, k'B) such that k'A ∈ (kA) O1(kB), k'B ∈ (kB)O(1), and |V(G')| ∈ O((kB · kB)1 -ε), for some ε > 0, then NP ⊆ coNP/poly and the polynomial-time hierarchy collapses. Using a different construction, we prove that if there is a polynomial-time algorithm that reduces any n-vertex instance into an equivalent instance (of a possibly different problem) that can be encoded in O(n2-ε) bits, then NP ⊆ coNP/poly.

The Subset Sum problem asks whether a given set of $n$ positive integers contains a subset of elements that sum up to a given target $t$. It is an outstanding open question whether the $O^*(2^{n/2})$-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", $O^*(2^{(0.5-\delta)n})$-time algorithm, with some constant $\delta > 0$. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size $\beta$, defined as the largest number of subsets of the $n$ input integers that yield the same sum. For every $\epsilon > 0$ we give a truly faster algorithm for instances with $\beta \leq 2^{(0.5-\epsilon)n}$, as well as instances with $\beta \geq 2^{0.661n}$. Consequently, we also obtain a characterization in terms of the popular density parameter $n/\log_2 t$: if all instances of density at least $1.003$ admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from novel combinations of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory., Comment: 14 pages

We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem

We investigate the Matrix Powering Positivity Problem, PosMatPow: given an m X m square integer matrix M, a linear function f: Z^{m X m} -> Z with integer coefficients, and a positive integer n (encoded in binary), determine whether f(M^n) \geq 0. We show that for fixed dimensions m of 2 and 3, this problem is decidable in polynomial time.

[Schaefer and Štefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of ∃ℝ as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, given a 3-player game, whether or not it has a Nash equilibrium with no probability exceeding a given rational is ∃ℝ-complete. Four more decision problems about Nash equilibria for 3-player games were very recently shown ∃ℝ-complete via a chain of individual, problem-specific reductions in [Garg et al., Proceedings of ICALP 2015] determining more such ∃ℝ-complete problems was posed there as an open problem. In this work, we deliver an extensive catalog of ∃ℝ-complete decision problems about Nash equilibria in 3-player games, thus resolving completely the open problem from [Garg et al., Proceedings of ICALP 2015]. Towards this end, we present a single and very simple, unifying reduction from the ∃ℝ-complete decision problem from [Schaefer and Štefankovic, Theory of Computing Systems, 2015] to (almost) all the decision problems about Nash equilibria that were before shown NP-complete for 2-player games in [Bilò and Mavronicolas, Proceedings of SAGT 2012 Conitzer and Sandholm, Games and Economic Behavior, 2008 Gilboa and Zemel, Games and Economic Behavior, 1989]. Encompassed in the catalog are the four decision problems shown ∃ℝ-complete in [Garg et al., Proceedings of ICALP 2015]. © Vittorio Bilò and Marios Mavronicolas licensed under Creative Commons License CC-BY. 47 Sponsors: Conference code: 119274 Cited By :4

We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be. Deciding if a group of items of total weight 2 could be packed into two knapsacks of unit capacity is already NP -hard and it thus rules out a constant-approximation algorithm for this problem in general. We then focus on the parameterized version where the total weight of items in each group is bounded by a factor δ of the total capacity of all knapsacks. Both approximation and inapproximability results with respect to δ are derived. We also show that, depending on whether the number of knapsacks is a constant or part of the input, the approximation ratio for the problem, as a function on δ, changes substantially, which has a clear difference from the classical multiple knapsack problem.

In this paper we focus on problems which do not admit a constant-factor approximation in polynomial time and explore how quickly their approximability improves as the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For Min Independent Dominating Set, Max Induced Path, Forest and Tree, for any r(n), a simple, known scheme gives an approximation ratio of r in time roughly rn/r. We show that, for most values of r, if this running time could be significantly improved the ETH would fail. For Max Minimal Vertex Cover we give a nontrivial √r-approximation in time 2n/r. We match this with a similarly tight result. We also give a log r-approximation for Min ATSP in time 2n/r and an r-approximation for Max Grundy Coloring in time rn/r. Furthermore, we show that Min Set Cover exhibits a curious behavior in this superpolynomial setting: for any δ > 0 it admits an mδ-approximation, where m is the number of sets, in just quasi-polynomial time. We observe that if such ratios could be achieved in polynomial time, the ETH or the Projection Games Conjecture would fail. © Édouard Bonnet, Michael Lampis and Vangelis Th. Paschos; licensed under Creative Commons License CC-BY.