FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |   ...   | 16 |

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

-- [ Page 13 ] --

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-defined, continuous, and strictly monotone function from R+ → R. Furthermore, wS = −1 + s∈S f (s) for all finite 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 define

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

The salient feature of this construction is that all sets Si are different, 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 significantly, 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 define 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 first 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 coefficient 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 coefficient 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 coefficients 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 inflations 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 different 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 define a class of graph inflations, Bounce inflations, and use the above to show that they give rise to distinct weight shifts along the reliability line of the Tutte polynomial. Bounce inflations 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.

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

Inflating 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 effect 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 simplified Bounce graph, and the old value w outside the simplified 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 inflations 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 coefficients by interpolation. By Proposition 5.2, evaluating these coefficients 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 first 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 sparsification, 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 inflation with the analysis in the proof of Lemma 5.6 suffice to show that every point is as hard as computing the coefficients 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 coefficients 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 } satisfies

–  –  –

Pages:     | 1 |   ...   | 11 | 12 || 14 | 15 |   ...   | 16 |

Similar works:

«Assessor’s guidelines for the SVQs in Amenity Horticulture at levels 2 and 3 and Amenity Horticulture Management at level 4 First edition: January 2003 Second edition: May 2008 Publication code: DB1772/2 Published by the Scottish Qualifications Authority The Optima Building, 58 Robertson Street, Glasgow, G2 7DQ, and Ironmills Road, Dalkeith, Midlothian, EH22 1LE The information in this publication may be reproduced in support of SQA qualifications. If it is reproduced, SQA should be clearly...»

«Rough Amusements The Story Of A Lelia Walker Patroness Of The Harlem Renaissance S Down Low Culture Lives by advantages are starting made of relationship and type lenders. Because I last 10 which is temporary people you must see they is Rough Amusements: The Story of A'Lelia Walker, Patroness of the Harlem Renaissance's Down-Low Culture again prior positive also. For spilling questions individual of how it have operating, where you are running just, how you fail making easily, what is taking...»

«TÖRTÉNELEM DOKTORI PROGRAM KUTATÁSI FÜZETEK Pordán Ildikó László Károly beszámolója Kossuth amerikai útjáról A Kutatási Füzetek a Janus Pannonius Tudományegyetem Európa és Magyarország a 19-20. században című történelem doktori (Ph.D.) programjának sorozata. Szerkesztők Ormos Mária Harsányi Iván Flodung János Soós Gábor Janus Pannonius Tudományegyetem Pécs, 1996 TARTALOM László Károly és naplója Kossuth Amerikában László Károly naplója Kossuth...»

«Cities Alliance Project Output Taj Ganj Slum Housing Upgrading Project Phase II: DPR for funding under RAY Citywide Slum Upgrading Plan (CSUP) for the Heritage City of Agra (India) P120112 This project output was created with Cities Alliance grant funding. Taj Ganj Slum Housing Upgrading Project, Phase-II Content List of Figures, tables and Graphs Check-List For Preparation / Appraisal Of DPR For Agra City under RAY Summary of Cost of DPR 1. Background 1.1. Introduction 1.2. Taj Trapezium Zone...»

«1 CURRICULUM VITAE CARMEN BENITO-VESSELS (301)405-6445(Office) (301) 530-5030 (Home) cbenito@umd.edu PERSONAL INFORMATION Full time Professor, since September 2006, in the Department of Spanish and Portuguese at the University of Maryland, College Park.EDUCATION PhD, Hispanic Languages and Literatures, University of California, Santa Barbara, 1982-1988. Major field of concentration: Spanish Medieval Literature. English Philology, University of Salamanca, Salamanca, Spain, 1979-1981. Portuguese...»

«Schriftliche Hausarbeit im Rahmen der zweiten staatlichen Prüfung für das Lehramt an Grund -, Hauptund Realschulen gemäß § 13 PVO-LehrII Thema der Arbeit: Erziehung zu mehr Fairness, dargestellt an dem fächerübergreifenden Unterrichtsvorhaben: „Fairplay faireint“ in einer zweiten Grundschulklasse Fach: Pädagogik vorgelegt von: Annika Warms im Studienseminar Verden Erstgutachter: C. Krause Zweitgutachter: W. Schmidtke Osterholz-Scharmbeck, 27.08.2005 Inhaltsverzeichnis...»

«Academic Advising Program Handbook College of Arts and Sciences The University of North Carolina at Chapel Hill August, 2013 Academic Eligibility 9 Eligibility Status 9 Calculating Transferred Semesters 11 Part-Time Classroom Studies Eligibility 11 Restoring Academic Eligibility 12 Add, Drop, Audit 13 Adding 13 Dropping 14 Auditing 15 Advisor-Student Contact 17 Appointments 17 Walk-Ins 18 Advising Notes 19 Appeals 21 Course Drop and Withdrawal Appeals 21 Probation Appeals 22 Grade Appeals 22...»

«i STUDY ON THERMAL MODEL FOR CALCULATING TRANSFORMER HOT SPOT TEMPERATURE JAMAL ALI RAMADAN DOFAN A thesis is submitted of the fulfillment of the requirements for the award of the degree of Master of Electrical & Electronic Engineering Faculty of Electrical & Electronic Engineering University Tun Hussein Onn Malaysia (UTHM) may 2011 V ABSTRACT A power transformer is a static piece of apparatus with two or more windings which, by electromagnetic induction, transforms a system of alternating...»

«People and Forests: a Case Study from Bénin, West Africa By Erika B. Kraus Submitted to the graduate degree program in African and African-American Studies and the Graduate Faculty of the University of Kansas in partial fulfillment of the requirements for the degree of Master of Arts. Chairperson, Beverly Mack, Ph.D. Peter Ukpokodu, Ph.D. Shawn Alexander, Ph.D. Date Defended: 10 April 2012 ii The Thesis Committee for Erika B. Kraus certifies that this is the approved version of the following...»

«A NŐK E G Y E T E M I T A N U L M Á N Y A I N A K KÉRDÉSE A BUDAPESTI ORVOSTUDOMÁNYI KARON 1896-1926 SZÖGI LÁSZLÓ X I X. század közepétől kezdődően előbb az Egyesült Államokban, majd Európa legtöbb or­ szágában is megnyíltak az egyetemek kapui a tanulni vágyó nők előtt. A z 1890-es évek elején már csak kevés európai országban tagadták meg a felvételre jelentkező nők kérését. A legkonzervatí­ vabbnak a cári Oroszország és Németország mellett éppen...»

«24 flight booking 24 flight booking Cheap Flights bis zu -50% | Cheap-Flights.Fluege.de Cheap Flights aller Airlines ab 19 im Vergleich. Cheap Flights buchen aircanada.com Cancelling a booking online Which bookings can be cancelled online You may cancel your booking online if: You originally booked your flight on aircanada.com; You are cancelling your British Airways Manage My Booking Check in online, print boarding passes and manage your British Airways booking. Specify dietary requirements,...»

«Bericht und Antrag des Regierungsrats an den Landrat _17. August 2010 Nr. 2010-440 R-150-13 Bericht und Antrag des Regierungsrats an den Landrat zum Postulat Paul Jans, Erstfeld, für eine wintersichere Zufahrt von Realp nach Hospental und umgekehrt 1. Ausgangslage Am 8. April 2009 reichten Landrat Paul Jans, Erstfeld, und die zweitunterzeichnenden Helen Simmen, Realp, und Paul Bennet, Andermatt, nach Artikel 83 der Geschäftsordnung (GO) des Landrats das Postulat Für eine wintersichere...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.