# «Gefördert durch die Deutsche Forschungsgemeinschaft im Rahmen des Graduiertenkollegs ’Methods for Discrete Structures’ (GRK 1408) Präsident der ...»

Let q and w be rational numbers with w = 0 and q ∈ {0, −w, −2w}. For all integers m ≥ 1, there exist sets S0,..., Sm of positive integers such that s ≤ O(log3 m) for all i, and (i) s∈Si

5. Exponential Time Counting Complexity

Furthermore, the sets Si can be computed in time polynomial in m.

Proof. Let b = |1 + q/w| and f (s) = 1 + q/(bs − 1) for s 0. Our choice of parameters ensures that b 0 and b = 1, so f is a well-deﬁned, continuous, and strictly monotone function from R+ → R. Furthermore, wS = −1 + s∈S f (s) for all ﬁnite sets S of positive even integers. Now let s0 ≥ 2 be an even integer such that f (s) is nonzero and has the same sign as f (s0 ) for all s ≥ s0. For i = 0,..., m, let b · · · b0 denote the binary expansion of i where = log m. Let ∆ 6 be a gap parameter that is an even integer and large, but only depends on q and w and is chosen later. We deﬁne

** Si = { s0 + ∆ log m · (2j + bj ) : 0 ≤ j ≤ }.**

The salient feature of this construction is that all sets Si are diﬀerent, of equal small cardinality, contain only positive even integers, and are from a range where f does not change sign. Most important for our analysis is that the elements of the Si are spaced apart signiﬁcantly, i.e., for i, j and any s ∈ Si and t ∈ Sj, either s = t or |s − t| ≥ ∆ log m. (P) From |Si | = log m + 1 and the fact that all numbers in the sets are bounded by O(log2 m), we immediately get (i).

To establish (ii), let 0 ≤ i j ≤ m. We want to show that wSi = wSj. Let us deﬁne S = Si \ Sj and T = Sj \ Si. From (5.12), we see by multiplying with (wSi ∩Sj + 1) on both sides that wS + 1 = wT + 1 is equivalent to wSi = wSj since wSi ∩Sj = −1.

It remains to show that s∈S f (s) = t∈T f (t). Equivalently,

Here we use the convention that for X ⊆ S ∪ T, the term bs is taken in the ﬁrst factor if s ∈ X ∩ S, and bt is taken in the second factor if t ∈ X ∩ T. Doing this for both terms of (5.13) and collecting terms we arrive at the equivalent claim

The largest exponent of b with nonzero coeﬃcient in (5.15) is S ∪ T − s1 and all other exponents are at least ∆ log m smaller than that. Similarly, the smallest exponent of b with nonzero coeﬃcient is s1 and all other exponents are at least ∆ log m larger. We will let X0 denote the term with the largest contribution in (5.14); so we set X0 = S ∪T \{s1 } for b 1 and X0 = {s1 } for b 1.

The total contribution of the remaining terms is h = X=X0 g(X). We prove (5.14) by showing |h| |g(X0 )|. From the triangle inequality and the fact that S ∪ T has at most 4m2 subsets X, we get |h| ≤ 4m2 · max |g(X)| ≤ 4m2 · 2|q − 1|1+log m · b X0 ±∆ log m X=X0 where the sign in ±∆ log m depends on whether b is larger or smaller than 1. If b 1, the sign is negative. In this case, notice that ∆ = ∆(q, w) can be chosen so that 4m2 · 2|q − 1|1+log m |q| · b∆ log m for all m ≥ 2. If b 1, we can similarly choose ∆ as to satisfy 4m2 · 2|q − 1|1+log m |q| · |1 − q||S|−1 · b−∆ log m. Thus, in both cases we have |h| |g(X0 )|, establishing (ii).

Points on the Hyperbolas We show Theorem 1.11 (iv), that evaluating Z at most points (q, w) with q ∈ {0, 1} is hard.

Proposition 5.4. Let (q, w) ∈ Q2 \{(4, −2), (2, −1), (2, −2)} with q ∈ {0, 1} and w = 0.

/ Computing Z(G; q, w) for a given simple graph G requires time exp(Ω(m/ log3 m)) under #ETH.

By (5.1), the points (4, −2), (2, −1), and (2, −2) in the (q, w)-plane correspond to the polynomial-time computable points (−1, −1), (−1, 0), and (0, −1) in the (x, y)-plane.

Proof. We reduce from the problem of computing the coeﬃcients of the polynomial v → Z(G; q, v), which requires time exp(Ω(m)) for q ∈ {0, 1} by Proposition 5.1 and Proposition 5.2. We interpolate as in the proof of Proposition 5.3, but instead of thickenings we use Theta inﬂations to keep the number of edges relatively small.

First we consider the degenerate case in which q = −w or q = −2w. For a positive integer constant k, let G be the k-thickening of G. This transformation shifts the weight to w with w = (1 + w)k − 1, which allows us to compute Z(G; q, w ) from Z(G ; q, w) using (5.10). In the case q = −w, we have 1 + w = 1 − q, which cannot be 1 or 0, but which can also not be −1 since then

5. Exponential Time Counting Complexity

Bounce Graphs The reliability line of the Tutte plane, i.e., the line x = 1, is not covered by the above since here q = 0 holds. On this line, the Tutte polynomial specializes to the reliability polynomial R(G; p) (with p = 1/y), an object studied in algebraic graph theory [GR01, Section 15.8]. Given a connected graph G and a probability p, R(G; p) is the probability that G stays connected if every edge independently fails with probability p. For example R( ; 3 ) = P r( ) + 5P r( ) = ( 2 )5 + 5 · 1 · ( 2 )4 = 112. Note that R(G; 1) = 0 for all connected graphs, so p = 1 is easy to evaluate – as it should be since it corresponds to the polynomial-time solvable point (1, 1) in the Tutte plane.

Along the reliability line, weight shift identities take a diﬀerent form. Using deletion– contraction identities we obtain the following rules, which are simple multi-weighted generalizations of [GJ08, Section 4.3].

** Lemma 5.4.**

Let G be a graph with edge weights given by w : E(G) → Q.

If ϕ(G) is obtained from G by replacing a single edge e ∈ E with a simple path of k edges P = {e1,..., ek } with w(ei ) = wi, then

Here w[e → w ] denotes the function w : E(G) → Q that is identical to w except at the point e where it is w (e) = w.

** Lemma 5.5.**

If ϕ(G) is obtained from G by replacing a single edge e ∈ E with a bundle of parallel edges B = {e1,..., ek } with w(ei ) = wi, then

These rules are transitive [GJ08, Lemma 1], and so can be freely combined for more intricate weight shifts. We deﬁne a class of graph inﬂations, Bounce inﬂations, and use the above to show that they give rise to distinct weight shifts along the reliability line of the Tutte polynomial. Bounce inﬂations are mildly inspired by l-byte numbers, in the sense that each has associated to it a sequence of length l, such that the lexicographic order of these sequences determines the size of the corresponding (shifted) weights.

Deﬁnition 5.2 (Bounce graph). For positive integers i (height) and s (width), an (i, s)-bounce is the graph obtained by identifying all the left and all the right endpoints of i simple paths of length s each. Given a sequence S = s1, s2,..., sl of l positive integers, the Bounce graph BS is the graph obtained by concatenating l bounces at their endpoints, where the i-th bounce is an (i, si )-bounce, i.e., its height is i and its width is si.

The number l is the length of the Bounce graph BS.

Inﬂating a graph by a Bounce graph shifts the weights on the reliability line as follows.

5. Exponential Time Counting Complexity Lemma 5.6. For any graph G with m edges, any sequence S = s1, s2,..., sl of positive integers, and any non-zero rational number w, we have

Proof. We start with G ⊗ BS and consider the eﬀect that replacing one of the m canonical copies of BS with a single edge e has. We show that, with ϕ denoting this operation,

where w takes the value w/si on every edge of the ith bounce of the simpliﬁed Bounce graph, and the old value w outside the simpliﬁed Bounce graph. Next, we successively replace each of its (i, 1)-bounces by a single edge to get a simple path ( ) of length l. This transformation is just an ’unthickening’ of each (i, 1)-bounce, and from (5.17) of Corollary 5.1 we know that it does not produce any new factors for the polynomial, but the weight of the ith edge in this path becomes

Finally, we compress the path into a single edge e. Then the claim in (5.18) follows by a single application of Lemma 5.4.

We now show that Bounce inﬂations provide a rich enough class of weight shifts. The ranges of w for which we prove this is general enough to allow for interpolation on the whole reliability line, and we make no attempt at extending the ranges. The proof for

w 9 is due to Husfeldt and Taslaman [HT10].

** Lemma 5.7.**

Let w be a rational number with w ∈ (−1, 0) or w ∈ (9, ∞). For all integers m ≥ 1, there exist sequences S0,..., Sm of positive integers such that (i) |E(BSi )| ≤ O(log2 m) for all i, and

We now claim that f is strictly decreasing in (4, ∞). This implies that ∆ 0 since w 9 guarantees a, b 4, and we get ∆ ≥ f (a) − f (b) 0. To prove the claim, we

5. Exponential Time Counting Complexity

Points on the Reliability Line We prove Theorem 1.11 (iii). For w 0, this is due to Husfeldt and Taslaman [HT10].

Proposition 5.5. Let w be a rational number with w = 0. Computing Z0 (G; 0, w) for a given simple graph G requires time exp(Ω(m/ log2 m)) under #ETH.

Proof. If w 0, we can pick a positive integer k big enough such that

This is the weight shift that corresponds to the 2-stretch of the k-thickening of G (Corollary 5.1). In any case we can compute Z(G; w, q) from Z(G ; w, q). The graph remains simple after any of these transformations, and the number of edges is only increased by a constant factor of at most 2k.

By the above, we can assume w.l.o.g. that w ∈ (−1, 0) or w 9. Lemma 5.7 then allows us to construct m+1 bounce graphs BS such that the corresponding weight shifts wS are all distinct by property (ii). By Lemma 5.6, we can compute the values Z0 (G; 0, wS ) from Z0 (G ⊗ BS ; 0, w), i.e., we get evaluations of v → Z0 (G; 0, v) at m + 1 distinct points. Since the degree of this polynomial is m, we obtain its coeﬃcients by interpolation. By Proposition 5.2, evaluating these coeﬃcients requires time exp(Ω(m)) under

5. Exponential Time Counting Complexity #ETH. By Lemma 5.7 (i), each G ⊗ BS has at most O(m log2 m) edges, which implies that computing Z0 (G; 0, w) for given G requires time exp(Ω(m/ log2 m)) as claimed.

Notes Results in this chapter are joint work with Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Most results appeared in [DHW10], but the hardness of the Tutte polynomial at x = 1 and y 1 is from [HT10].

6. Summary and Open Problems In the ﬁrst part of this thesis, we introduced a model of communication that captures various settings of interest in the theory of computing. For NP-complete problems like d-Sat, d-Vertex Cover, d-Clique, and d-Set Matching, we showed that trivial protocols are essentially optimal as function of the witness size, unless the polynomialtime hierarchy collapses. Under the hypothesis that the latter does not happen, the result implies tight lower bounds for parameters captured by the communication model, including the size of PCPs, and polynomial-time sparsiﬁcation, kernelization, and lossy compression. Under stronger hypotheses similar results hold for larger time bounds.

Future directions include more applications with an active oracle, exploiting the full power of our oracle communication model; we presented some in Section 3.6. Another direction regards the extension to the randomized setting with false negatives, and with false positives as well as false negatives; we know how to handle false positives only. In light of the hardness results for OR-problems, it is natural to ask whether an analogue for AND-problems exists, and such a result would have consequences for the kernelizability of problems like computing the tree-width. Finally, can we relax the hypothesis coNP ⊆ NP/poly to the minimal P = NP?

Our results for the Tutte polynomial leave open the line y = 1 except for the point (1, 1), even in the case of multigraphs. That line corresponds to counting the number of forest weighted by the number of edges, i.e., T (G; 1+1/w, 1) ∼ F (G; w) = forests F w|F |.

Thickening and Theta inﬂation with the analysis in the proof of Lemma 5.6 suﬃce to show that every point is as hard as computing the coeﬃcients of F (G; w) without increasing the number of vertices for multigraphs and with an increase in the number of edges by a factor of O(log2 m) in the case of simple graphs. However, we do not know that computing those coeﬃcients requires exponential time. And of course, it would be nice to improve our conditional lower bounds exp(Ω(n/ poly log n)) to match the corresponding upper bounds exp(O(n)).

A. Behrend’s Construction We now prove Lemma 4.1, following an elegant construction due to Behrend [Beh46], which improves on the original construction due to Salem and Spencer [SS42].

** Lemma 4.1 (restated).**

For every positive integer p there exists a subset A ⊆ Zp of size at least p1−o(1) which contains no nontrivial arithmetic progressions of length three.

Furthermore, such a set A can be determined in time polynomial in p.

Proof. Let p be a positive integer. We want to construct a set A ⊆ Zp of size p1−o(1) that contains no nontrivial arithmetic progressions of length three over Zp.

For positive integers d, m and a real r to be chosen later, let Sr ⊆ Rd denote the

**d-dimensional sphere of radius r restricted to vectors whose components are from Zm :**

This is the type of property we need except that we want it for a subset of integers rather than vectors with integer coordinates. We can transform Sr into a set of integers and maintain (A.1) by applying a linear mapping. : Nd → N that is 1-to-1 on Zd 2m−1.

Then the set Sr = { a | a ∈ Sr } satisﬁes