
We study the Directed Feedback Vertex Set problem parameterized by the
treewidth of the input graph. We prove that unless the Exponential Time
Hypothesis fails, the problem cannot be solved in time $2^{o(t\log t)}\cdot
n^{\mathcal{O}(1)}$ on general directed graphs, where $t$ is the treewidth of
the underlying undirected graph. This is matched by a dynamic programming
algorithm with running time $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$.
On the other hand, we show that if the input digraph is planar, then the
running time can be improved to $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$.

For even $k$, the matchings connectivity matrix $M_k$ is a binary matrix
indexed by perfect matchings of the complete $k$vertex graph; the entry at a
pair of matchings is $1$ iff their union forms a single cycle. Previous work
has found connections between the asymptotic rank of $M_k$ and the complexity
of the Hamiltonian Cycle problem: Cygan et al. (STOC 2013) showed that the rank
of $M_k$ over $\mathbb Z_2$ is $\Theta(\sqrt 2^k)$ and used this to give an
$O^*((2+\sqrt{2})^{\mathsf{pw}})$ time algorithm for counting Hamiltonian
cycles modulo $2$ on graphs of pathwidth $\mathsf{pw}$. The same authors
complemented their algorithm by an essentially tight lower bound under SETH.
This bound crucially relied on a large permutation submatrix within $M_k$,
which enabled a "pattern propagation" technique.
We present a new technique to simulate a similar "pattern propagation" when
only a blackbox lower bound on the asymptotic rank of $M_k$ is given. Given
appropriate rank bounds, our technique yields lower bounds for counting
Hamiltonian cycles (also modulo fixed primes $p$) parameterized by pathwidth.
To apply this technique, we prove that the rank of $M_k$ over $\mathbb Q$ is
$4^k / \mathrm{poly}(k)$, using the representation theory of the symmetric
group and insights from algebraic combinatorics. We also show that the rank of
$M_k$ over $\mathbb Z_p$ is $\Omega(1.56^k)$ for any prime $p\neq 2$.
As a consequence, we obtain that Hamiltonian cycles cannot be counted in time
$O^*((6\epsilon)^{\mathsf{pw}})$ for any $\epsilon>0$ unless SETH fails, which
is tight due to an algorithm by Bodlaender et al. (ICALP 2013). We also obtain
that Hamiltonian cycles cannot be counted modulo primes $p\neq 2$ in time
$O^*(3.56^\mathsf{pw})$, in contrast to the
$O^*((2+\sqrt{2})^{\mathsf{pw}})=O^*(3.42^{\mathsf{pw}})$ time algorithm for
counting mod $2$ by Cygan et al. (STOC 2013).

In this paper, we develop new tools and connections for exponential time
approximation. In this setting, we are given a problem instance and a parameter
$\alpha>1$, and the goal is to design an $\alpha$approximation algorithm with
the fastest possible running time. We show the following results:
 An $r$approximation for maximum independent set in $O^*(\exp(\tilde O(n/r
\log^2 r+r\log^2r)))$ time,
 An $r$approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log
r+r\log^2r)))$ time,
 A $(21/r)$approximation for minimum vertex cover in
$O^*(\exp(n/r^{\Omega(r)}))$ time, and
 A $(k1/r)$approximation for minimum $k$hypergraph vertex cover in
$O^*(\exp(n/(kr)^{\Omega(kr)}))$ time.
(Throughout, $\tilde O$ and $O^*$ omit $\mathrm{polyloglog}(r)$ and factors
polynomial in the input size, respectively.) The best known time bounds for all
problems were $O^*(2^{n/r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008].
For maximum independent set and chromatic number, these bounds were
complemented by $\exp(n^{1o(1)}/r^{1+o(1)})$ lower bounds (under the
Exponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit,
2014 (Ph.D. Thesis)]. Our results show that the naturallylooking
$O^*(2^{n/r})$ bounds are not tight for all these problems. The key to these
algorithmic results is a sparsification procedure, allowing the use of better
approximation algorithms for bounded degree graphs. For obtaining the first two
results, we introduce a new randomized branching rule.
Finally, we show a connection between PCP parameters and exponentialtime
approximation algorithms. This connection together with our independent set
algorithm refute the possibility to overly reduce the size of Chan's PCP [Chan,
2016]. It also implies that a (significant) improvement over our result will
refute the gapETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].

The generalized kserver problem is a farreaching extension of the kserver
problem with several applications. Here, each server $s_i$ lies in its own
metric space $M_i$. A request is a ktuple $r = (r_1,r_2,\dotsc,r_k)$ and to
serve it, we need to move some server $s_i$ to the point $r_i \in M_i$, and the
goal is to minimize the total distance traveled by the servers. Despite much
work, no f(k)competitive algorithm is known for the problem for k > 2 servers,
even for special cases such as uniform metrics and lines.
Here, we consider the problem in uniform metrics and give the first
f(k)competitive algorithms for general k. In particular, we obtain
deterministic and randomized algorithms with competitive ratio $O(k 2^k)$ and
$O(k^3 \log k)$ respectively. Our deterministic bound is based on a novel
application of the polynomial method to online algorithms, and essentially
matches the longknown lower bound of $2^k1$. We also give a
$2^{2^{O(k)}}$competitive deterministic algorithm for weighted uniform
metrics, which also essentially matches the recent doubly exponential lower
bound for the problem.

We present space efficient Monte Carlo algorithms that solve Subset Sum and
Knapsack instances with $n$ items using $O^*(2^{0.86n})$ time and polynomial
space, where the $O^*(\cdot)$ notation suppresses factors polynomial in the
input size. Both algorithms assume random readonly access to random bits.
Modulo this mild assumption, this resolves a longstanding open problem in
exact algorithms for NPhard problems. These results can be extended to solve
Binary Linear Programming on $n$ variables with few constraints in a similar
running time. We also show that for any constant $k\geq 2$, random instances of
$k$Sum can be solved using $O(n^{k0.5}polylog(n))$ time and $O(\log n)$
space, without the assumption of random access to random bits.
Underlying these results is an algorithm that determines whether two given
lists of length $n$ with integers bounded by a polynomial in $n$ share a common
value. Assuming random readonly access to random bits, we show that this
problem can be solved using $O(\log n)$ space significantly faster than the
trivial $O(n^2)$ time algorithm if no value occurs too often in the same list.

The worstcase fastest known algorithm for the Set Cover problem on universes
with $n$ elements still essentially is the simple $O^*(2^n)$time dynamic
programming algorithm, and no nontrivial consequences of an $O^*(1.01^n)$time
algorithm are known. Motivated by this chasm, we study the following natural
question: Which instances of Set Cover can we solve faster than the simple
dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm
that determines the existence of a set cover of size $\sigma n$ in
$O^*(2^{(1\Omega(\sigma^4))n})$ time. Our approach is also applicable to Set
Cover instances with exponentially many sets: By reducing the task of finding
the chromatic number $\chi(G)$ of a given $n$vertex graph $G$ to Set Cover in
the natural way, we show there is an $O^*(2^{(1\Omega(\sigma^4))n})$time
randomized algorithm that given integer $s=\sigma n$, outputs NO if $\chi(G) >
s$ and YES with constant probability if $\chi(G)\leq s1$.
On a high level, our results are inspired by the `representation method' of
HowgraveGraham and Joux~[EUROCRYPT'10] and obtained by only evaluating a
randomly sampled subset of the table entries of a dynamic programming
algorithm.

The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path
Decomposition (MSPD) problems ask for a given nvertex graph G and integer k,
what is the minimum number of bags of a tree decomposition (respectively, path
decomposition) of G of width at most k. The problems are known to be
NPcomplete for each fixed $k\geq 4$. We present algorithms that solve both
problems for fixed k in $2^{O(n/ \log n)}$ time and show that they cannot be
solved in $2^{o(n / \log n)}$ time, assuming the Exponential Time Hypothesis.

Two sets $A, B \subseteq \{0, 1\}^n$ form a Uniquely Decodable Code Pair
(UDCP) if every pair $a \in A$, $b \in B$ yields a distinct sum $a+b$, where
the addition is over $\mathbb{Z}^n$. We show that every UDCP $A, B$, with $A
= 2^{(1\epsilon)n}$ and $B = 2^{\beta n}$, satisfies $\beta \leq 0.4228
+\sqrt{\epsilon}$. For sufficiently small $\epsilon$, this bound significantly
improves previous bounds by Urbanke and Li~[Information Theory Workshop '98]
and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound $\beta$
by $0.4921$ and $0.4798$, respectively, as $\epsilon$ approaches $0$.

In the subset sum problem we are given n positive integers along with a
target integer t. A solution is a subset of these integers summing to t. In
this short note we show that for a given subset sum instance there is a proof
of size $O^*(\sqrt{t})$ of what the number of solutions is that can be
constructed in $O^*(t)$ time and can be probabilistically verified in time
$O^*(\sqrt{t})$ with at most constant error probability. Here, the $O^*()$
notation omits factors polynomial in the input size $n\log(t)$.

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 worstcase 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.

The field of exact exponential time algorithms for NPhard problems has
thrived over the last decade. While exhaustive search remains asymptotically
the fastest known algorithm for some basic problems, difficult and nontrivial
exponential time algorithms have been found for a myriad of problems, including
Graph Coloring, Hamiltonian Path, Dominating Set and 3CNFSat. In some
instances, improving these algorithms further seems to be out of reach. The
CNFSat problem is the canonical example of a problem for which the trivial
exhaustive search algorithm runs in time O(2^n), where n is the number of
variables in the input formula. While there exist nontrivial algorithms for
CNFSat that run in time o(2^n), no algorithm was able to improve the growth
rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is
the optimal growth rate. The strong exponential time hypothesis (SETH) by
Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that,
for every epsilon<1, there is a (large) integer k such that that kCNFSat
cannot be computed in time 2^{epsilon n}.
In this paper, we show that, for every epsilon < 1, the problems Hitting Set,
Set Splitting, and NAESat cannot be computed in time O(2^{epsilon n}) unless
SETH fails. Here n is the number of elements or variables in the input. For
these problems, we actually get an equivalence to SETH in a certain sense. We
conjecture that SETH implies a similar statement for Set Cover, and prove that,
under this assumption, the fastest known algorithms for Steinter Tree,
Connected Vertex Cover, Set Partitioning, and the pseudopolynomial time
algorithm for Subset Sum cannot be significantly improved. Finally, we justify
our assumption about the hardness of Set Cover by showing that the parity of
the number of set covers cannot be computed in time O(2^{epsilon n}) for any
epsilon<1 unless SETH fails.

A multicast game is a network design game modelling how selfish
noncooperative agents build and maintain onetomany network communication.
There is a special source node and a collection of agents located at
corresponding terminals. Each agent is interested in selecting a route from the
special source to its terminal minimizing the cost. The mutual influence of the
agents is determined by a cost sharing mechanism, which evenly splits the cost
of an edge among all the agents using it for routing. In this paper we provide
several algorithmic and complexity results on finding a Nash equilibrium
minimizing the value of Rosenthal potential. Let n be the number of agents and
G be the communication network. We show that
 For a given strategy profile s and integer k>=1, there is a local search
algorithm which in time n^{O(k)}G^{O(1)} finds a better strategy profile, if
there is any, in a kexchange neighbourhood of s. In other words, the algorithm
decides if Rosenthal potential can be decreased by changing strategies of at
most k agents;
 The running time of our local search algorithm is essentially tight: unless
FPT= W[1], for any function f(k), searching of the kneighbourhood cannot be
done in time f(k)G^{O(1)}.
The key ingredient of our algorithmic result is a subroutine that finds an
equilibrium with minimum potential in 3^nG^{O(1)} time. In other words,
finding an equilibrium with minimum potential is fixedparameter tractable when
parameterized by the number of agents.

Dynamic programming on tree decompositions is a frequently used approach to
solve otherwise intractable problems on instances of small treewidth. In recent
work by Bodlaender et al., it was shown that for many connectivity problems,
there exist algorithms that use time, linear in the number of vertices, and
single exponential in the width of the tree decomposition that is used. The
central idea is that it suffices to compute representative sets, and these can
be computed efficiently with help of Gaussian elimination.
In this paper, we give an experimental evaluation of this technique for the
Steiner Tree problem. A comparison of the classic dynamic programming algorithm
and the improved dynamic programming algorithm that employs the table reduction
shows that the new approach gives significant improvements on the running time
of the algorithm and the size of the tables computed by the dynamic programming
algorithm, and thus that the rank based approach from Bodlaender et al. does
not only give significant theoretical improvements but also is a viable
approach in a practical setting, and showcases the potential of exploiting the
idea of representative sets for speeding up dynamic programming algorithms.

It is well known that many local graph problems, like Vertex Cover and
Dominating Set, can be solved in 2^{O(tw)}V^{O(1)} time for graphs G=(V,E)
with a given tree decomposition of width tw. However, for nonlocal problems,
like the fundamental class of connectivity problems, for a long time we did not
know how to do this faster than tw^{O(tw)}V^{O(1)}. Recently, Cygan et al.
(FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity
problems running in time $c^{tw}V^{O(1)} for a small constant c, e.g., for
Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether
randomization is necessary to achieve this runtime; furthermore, it is
desirable to also solve counting and weighted versions (the latter without
incurring a pseudopolynomial cost in terms of the weights).
We present two new approaches rooted in linear algebra, based on matrix rank
and determinants, which provide deterministic c^{tw}V^{O(1)} time algorithms,
also for weighted and counting versions. For example, in this time we can solve
the traveling salesman problem or count the number of Hamiltonian cycles. The
rankbased ideas provide a rather general approach for speeding up even
straightforward dynamic programming formulations by identifying "small" sets of
representative partial solutions; we focus on the case of expressing
connectivity via sets of partitions, but the essential ideas should have
further applications. The determinantbased approach uses the matrix tree
theorem for deriving closed formulas for counting versions of connectivity
problems; we show how to evaluate those formulas via dynamic programming.

For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a
matrix that has rows and columns both labeled by all perfect matchings of the
complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is
a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of
the Hamiltonicity problem, we present three results on the structure of H_t: We
first show that H_t has rank at most 2^{t/21} over GF(2) via an appropriate
factorization that explicitly provides families of matchings X_t forming bases
for H_t. Second, we show how to quickly change representation between such
bases. Third, we notice that the sets of matchings X_t induce permutation
matrices within H_t.
Subsequently, we use the factorization to obtain an 1.888^n n^{O(1)} time
Monte Carlo algorithm that solves the Hamiltonicity problem in directed
bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles
modulo two in directed bipartite or undirected graphs in the same time bound.
Moreover, we use the fast basis change algorithm from the second result to
present a Monte Carlo algorithm that given an undirected graph on n vertices
along with a path decomposition of width at most pw decides Hamiltonicity in
(2+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that
for every \epsilon >0 this cannot be improved to
(2+\sqrt{2}\epsilon)^{pw}n^{O(1)} time unless the Strong Exponential Time
Hypothesis fails, i.e., a faster algorithm for this problem would imply the
breakthrough result of a (2\epsilon)^n time algorithm for CNFSat.

Many combinatorial problems involving weights can be formulated as a
socalled ranged problem. That is, their input consists of a universe $U$, a
(succinctlyrepresented) set family $\mathcal{F} \subseteq 2^{U}$, a weight
function $\omega:U \rightarrow \{1,...,N\}$, and integers $0 \leq l \leq u \leq
\infty$. Then the problem is to decide whether there is an $X \in \mathcal{F}$
such that $l \leq \sum_{e \in X}\omega(e) \leq u$. Wellknown examples of such
problems include Knapsack, Subset Sum, Maximum Matching, and Traveling
Salesman. In this paper, we develop a generic method to transform a ranged
problem into an exact problem (i.e. a ranged problem for which $l=u$). We show
that our method has several intriguing applications in exact exponential
algorithms and parameterized complexity, namely:
 In exact exponential algorithms, we present new insight into whether Subset
Sum and Knapsack have efficient algorithms in both time and space. In
particular, we show that the time and space complexity of Subset Sum and
Knapsack are equivalent up to a small polynomial factor in the input size. We
also give an algorithm that solves sparse instances of Knapsack efficiently in
terms of space and time.  In parameterized complexity, we present the first
kernelization results on weighted variants of several wellknown problems. In
particular, we show that weighted variants of Vertex Cover, Dominating Set,
Traveling Salesman and Knapsack all admit polynomial randomized Turing kernels
when parameterized by $U$.
Curiously, our method relies on a technique more commonly found in
approximation algorithms.

We study classes of Dynamic Programming (DP) algorithms which, due to their
algebraic definitions, are closely related to coefficient extraction methods.
DP algorithms can easily be modified to exploit sparseness in the DP table
through memorization. Coefficient extraction techniques on the other hand are
both spaceefficient and parallelisable, but no tools have been available to
exploit sparseness.
We investigate the systematic use of homomorphic hash functions to combine
the best of these methods and obtain improved spaceefficient algorithms for
problems including LINEAR SAT, SET PARTITION, and SUBSET SUM. Our algorithms
run in time proportional to the number of nonzero entries of the last segment
of the DP table, which presents a strict improvement over sparse DP. The last
property also gives an improved algorithm for CNF SAT with sparse projections.

For the vast majority of local graph problems standard dynamic programming
techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input
graph. On the other hand, for problems with a global requirement (usually
connectivity) the bestknown algorithms were naive dynamic programming schemes
running in tw^O(tw) V^O(1) time.
We breach this gap by introducing a technique we dubbed Cut&Count that allows
to produce c^tw V^O(1) Monte Carlo algorithms for most connectivitytype
problems, including Hamiltonian Path, Feedback Vertex Set and Connected
Dominating Set, consequently answering the question raised by Lokshtanov, Marx
and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable
complexity assumptions) the gap cannot be breached for some problems for which
Cut&Count does not work, like CYCLE PACKING.
The constant c we obtain is in all cases small (at most 4 for undirected
problems and at most 6 for directed ones), and in several cases we are able to
show that improving those constants would cause the Strong Exponential Time
Hypothesis to fail.
Our results have numerous consequences in various fields, like FPT
algorithms, exact and approximate algorithms on planar and Hminorfree graphs
and algorithms on graphs of bounded degree. In all these fields we are able to
improve the bestknown results for some problems.