FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 16 |

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

-- [ Page 11 ] --

The generalization to d-uniform hypergraphs follows by using polynomials of degree d−1 instead of linear functions over Fq. Their use guarantees requirement (i) in Lemma 3.3.

Regarding requirement (ii), the following proof shows that the case d 2 reduces to the case d = 2. For arbitrary d ≥ 2, we fulfill requirement (ii) by restricting the coefficient of degree d − 1 to a set that contains no nontrivial arithmetic progressions of length three, namely the set A ⊆ Fq determined in Lemma 4.1.

Lemma 3.3 (restated).

For any integers p ≥ d ≥ 2 and t 0 there exists an p-partite d-uniform hypergraph P on O p · max(p, t1/d+o(1) ) vertices such that (i) the hyperedges of P partition into t cliques K1,..., Kt on p vertices each, and (ii) P contains no cliques on p vertices other than the Ki ’s.

Furthermore, for any fixed d, the hypergraph P and the Ki ’s can be constructed in time polynomial in p and t.

Proof (of Lemma 3.3). Let q be the smallest prime such that q ≥ p and |A| · q d−1 ≥ t, where A denotes the set given by Lemma 4.1. We have that q = O(max(p, t1/d+o(1) )) and can compute q and the set A in time polynomial in p and t.

Let V (P ) = [p] × Fq. We consider polynomials of degree at most d − 1 over Fq whose coefficient of xd−1 belongs to A. Note that there are |A| · q d−1 ≥ t such polynomials. For i ∈ [t], let hi denote the ith such polynomial in lexicographic order, and let Ki be the complete d-uniform hypergraph on vertex set V (Ki ) = {(j, hi (j)) | j ∈ [p]}. We define the d-uniform hypergraph P as the union of the t cliques Ki. The hypergraphs P and Ki can be constructed in time polynomial in p and t.

In order to argue property (i), it suffices to observe that every hyperedge of P is contained in at most one of the Ki ’s. This follows because the requirement that a given hyperedge of P belongs to Ki is equivalent to stipulating the value of hi on d distinct values j ∈ [p], which uniquely determines hi as a polynomial of degree at most d − 1 over Fq, and therefore determines i.

In order to argue property (ii), we need to establish the following for any function h : [p] → Fq : If for every subset D ⊆ [p] of size d there exists an i ∈ [t] such that h

4. Packing Edge-disjoint Cliques and hi agree on D, then there exists an i ∈ [t] such that h and hi agree on all of [p]. The property follows by applying the next claim to successive values of j ∈ [p − d], where qk denotes the polynomial hi which the hypothesis gives for the subset D = [j, j + d] \ {k}.

Claim. For each k ∈ [j, j + d], let qk be a polynomial of degree at most d − 1 such that the set of coefficients of degree d − 1 of the qk ’s contains no nontrivial arithmetic progression of length three. If for all k, ∈ [j, j + d], the polynomials qk and q agree on [j, j + d] \ {k, }, then the polynomials qk are all the same.

We prove the claim by induction on d. We already argued the base case d = 2, captured by Figure 4.1b, earlier in Section 4. For the inductive step, assume the claim holds for d−1 and let us prove it for d. Let qj,..., qj+d be polynomials as in the claim. For each k ∈ [j, j + d − 1], define qk as the difference quotient ∆j+d (qk ), i.e., qk : [j, j + d − 1] → Fq such that qk (x) = (qk (x) − qk (j + d))/(x − j − d) for x ∈ [j, j + d − 1]. Note that qk is a polynomial of degree at most d − 2 whose coefficient of degree d − 2 equals the coefficient of qk of degree xd−1. Moreover, for k, ∈ [j, j + d − 1], the polynomials qk and q agree on each x ∈ [j, j + d − 1] \ {k, } because the polynomials qk and q agree on both x and j + d. Thus, by the induction hypothesis, all polynomials qk are the same. By the definition of qk = ∆j+d (qk ) and the fact that the polynomials qk for k ∈ [j, j + d − 1] agree on j + d, this implies that the polynomials qk for k ∈ [j, j + d − 1] are all the same, say q. All that remains to show is that the polynomial qj+d also coincides with q. The latter follows because qj+d is a polynomial of degree at most d − 1 which agrees with the polynomial q of degree at most d − 1 on all d points in [j, j + d − 1].

Related Constructions After we developed our construction we learned about similar applications of high-density subsets of the integers without nontrivial arithmetic progressions of length three.

Back in 1976, Ruzsa and Szemerédi [RS78] constructed dense three-partite graphs whose edges partition into triangles and that contain no other triangles. Their construction corresponds to the case (d, s) = (2, 3) of our Packing Lemma, and appears between any three consecutive columns of our construction for d = 2 and general p. Our geometric derivation of the arithmetic progression condition (4.1), as captured in Figure 4.1b, may be new; all the derivations we have found in the literature work by manipulating equations in a – to us – less intuitive way.

Different aspects of the Ruzsa-Szemerédi construction matter for the various applications we know of in the theory of computing. For their soundness analysis of graph tests for linearity, Håstad and Wigderson [HW03] use the interpretation that for each of the q points in the first column, the triangles involving that point span an induced matching of q 1−o(1) edges between the other columns.

Another application area is the lower bounds for testing the graph property of being F -free, where F is some fixed graph. An -tester for this property accepts all graphs that are F -free, and rejects all graphs that are at least away from being F -free, i.e., from which at least n2 edges need to be removed to make it F -free [GGR98]. A strategy for proving lower bounds on the number of queries of such a tester is to construct highdensity graphs G with the following properties: (i) the edges of G partition into copies of F, and (ii) G contains few other copies of F so the total number of copies of F in G is significantly less than expected in a random graphs of the same density as G [Alo02].

Qualitatively, (i) implies that G is far from being F -free, and (ii) implies that testers with few queries have a small probability of detecting a violation of F -freeness on input G.

Alon and coauthors [Alo02, AS06, AS04, AKKR08, AS05] constructed such graphs G for various F based on the work of Ruzsa and Szemerédi [RS78].

The requirements for our application are similar but not identical to the ones for property testing. On the one hand we only need to consider the cases where F is a clique; on the other hand the graphs G cannot contain any copy of F other than those in which the edges partition. Our actual construction is very similar to the one Alon and Shapira [AS05] develop. Their construction would also work for our purposes. Our proof differs from theirs and makes the arithmetic progression condition more transparent. Our construction slightly improves1 on theirs as we only restrict the highest-order coefficient to the set A, whereas they restrict all coefficients to that set.

Notes The content of this chapter is joint work with Dieter van Melkebeek and appeared in [DvM10].

This allows us to relax the condition q( ) = max{m : (f (m))k ≥ } in Lemma 4.1 of [AS05] to q( ) =

–  –  –

5. Exponential Time Counting Complexity

5.1. Counting Independent Sets In this section, we establish Theorem 1.9, the hardness of counting independent sets and of #2-Sat. For the proof, we make use of the ETH-hardness of the following problem.

Name Unique 3-Sat.

Input 3-CNF formula ϕ with m clauses and at most one satisfying assignment.

Decide Is ϕ satisfiable?

Calabro et al. [CIKP03] use an isolation lemma for d-CNF formulas to show that solving this problem in subexponential time implies that the (randomized) exponential time hypothesis fails.

Theorem 5.1 (Corollary 2 of [CIKP03]).

ETH holds if and only if Unique 3-Sat requires time exp(Ω(m)).

We are now in the position to prove Theorem 1.9.

Theorem 1.9 (restated).

Counting independent sets and #2-Sat both require time exp(Ω(m)) under ETH, where m is the number of edges and clauses, respectively.

Proof. Let ϕ be an instance of Unique 3-Sat with m clauses. We construct a graph G with O(m) edges that has an odd number of independent sets if and only if ϕ is satisfiable.

For each variable x, we introduce vertices x and x, and the edge (xx). This makes sure that any independent set of G chooses at most one of {x, x}, so we can interpret the independent set as a partial assignment to the variables of ϕ. For each clause c = ( 1 ∨ 2 ∨ 3 ) of ϕ, we introduce a clique in G that consists of seven vertices c1,..., c7.

These vertices correspond to the seven partial assignments that assign truth values to the literals 1, 2, and 3 n such a way that c is satisfied. Any independent set of G contains at most one ci for each clause c. To ensure that the independent set chooses the variables and partial assignments of the clauses consistently, we add an edge for every ci and every variable x occurring in the clause c: If the partial assignment that corresponds to ci sets x to true, we add (ci x) to G; otherwise, we add (ci x) to G. To finalize the construction, we introduce guard vertices gx and gc for every variable x and every clause c, along with the edges (gx x), (gx x), and (gc ci ) for i = 1,..., 7.

We now prove that G has the required properties. First, any independent set contains at most n literal vertices and at most m clause vertices. Good independent sets are those that contain exactly n literal and m clause vertices (and no guard vertex). Good independent sets correspond to the satisfying assignments of ϕ in a natural way. We

5. Exponential Time Counting Complexity

now show that the number of bad independent sets is even. For this, let S be a bad independent set, that is, S is disjoint from {x, x} for some x or it is disjoint from {c1,..., c7 } for some clause c. By construction, the neighborhood of either gx or gc is disjoint from S. Let g be the lexicographically first guard vertex whose neighborhood is disjoint from S. Both the sets S \ {g} and S ∪ {g} are bad independent sets and S is one of these sets. Formally, we can therefore define a function that maps these sets onto each other. This function is a well-defined involution on the set of bad independent sets, and it does not have any fixed points. Therefore, the number of bad independent sets is even, and the parity of the number of independent sets of G is equal to the parity of the number of satisfying assignments of ϕ.

The above reduction shows that an exp(o(m))-time algorithm for counting independent sets modulo 2 implies an exp(o(m))-time algorithm for Unique 3-Sat. By Theorem 5.1, this implies that ETH fails.

To establish the hardness of #2-Sat, we reduce from counting independent sets. Let G be a graph. For each vertex v, we introduce a variable v, and each edge (uv) becomes a clause (u ∨ v). The satisfying assignments of the so constructed 2-CNF formula are in one-to-one correspondence with the independent sets of G.

5.2. The Permanent This section contains the proof of Theorem 1.10. With [0, n] = {0, 1,..., n} we establish the reduction chain #3-Sat Perm−1,0,1 Perm[0,n] Perm01 while taking care of the instance sizes.

Theorem 1.10 (restated).

(i) Perm−1,0,1 and Perm[0,n] require time exp(Ω(m)) under #ETH.

(ii) Perm01 requires time exp(Ω(m/ log n)) under #ETH.

(iii) Perm01 requires time exp(Ω(m)) under ETH.

Proof. To establish (i), we reduce #3-Sat in polynomial time to Perm−1,0,1 such that 3CNF formulas ϕ with m clauses are mapped to graphs G with O(m) edges. For technical reasons, we preprocess ϕ such that every variable x occurs equally often as a positive literal and as a negative literal x (e.g., by adding trivial clauses of the form (x ∨ x ∨ x)

¯ ¯¯

to ϕ). We construct G with O(m) edges and weights w : E → {±1} such that #Sat(ϕ) can be derived from per G in polynomial time. For weighted graphs, the permanent is

–  –  –

The sum above is over all cycle covers C of G, that is, subgraphs (V, C) with an in- and outdegree of 1 at every vertex.

In Figure 5.1, the gadgets of the construction are depicted. For every variable x that occurs in ϕ, we add a selector gadget to G. For every clause c = 1 ∨ 2 ∨ 3 of ϕ, we

–  –  –

add a clause gadget to G. Finally, we connect the edge labelled by a literal in the selector gadget with all occurrences of in the clause gadgets, using equality gadgets.

This concludes the construction of G.

The number of edges of the resulting graph G is linear in the number of clauses. The correctness of the reduction follows along the lines of [Pap94] and [BD07]. The satisfying assignments stand in bijection to cycle covers of weight (−1)i 2j where i (resp. j) is the number of occurrences of literals set to false (resp. true) by the assignment, and all other cycle covers sum up to 0. Since we preprocessed ϕ such that i = j holds and i is constant over all assignments, we obtain per G = (−2)i · #Sat(ϕ).

For the second part of (i), we reduce Perm−1,0,1 in polynomial time to Perm[0,n] by interpolation: On input G, we conceptually replace all occurrences of the weight −1 by a variable x and call this new graph Gx. We can assume that only loops have weight x in Gx because the output graph G from the previous reduction has weight −1 only on loops. Then p(x) = per Gx is a polynomial of degree d ≤ n.

If we replace x by a value a ∈ [0, n], then Ga is a weighted graph with as many edges as G. As a consequence, we can use the oracle to compute per Ga for a = 0,..., d and then interpolate, to get the coefficients of the polynomial p(x). At last, we return the value p(−1) = per G. This completes the reduction, which queries the oracle d+1 graphs that have at most m edges each.

Pages:     | 1 |   ...   | 9 | 10 || 12 | 13 |   ...   | 16 |

Similar works:

«eGovernment-Standards Seite 1 von 36 eCH-0018: XML Best Practices Name XML Best Practices Standard-Nummer eCH-0018 Kategorie Standard Reifegrad experimental Status Genehmigt Ausgabedatum 2005-06-21 Gültig seit 2005-08-25 Gültigkeitsdauer Version 1.0 Ersetzt Standard Basiert auf Änderungen Sprachen Deutsch und Französisch Herausgeber / Verein eCH, Laupenstrasse 18a, 3008 Bern Vertrieb 031 560 00 20 / info@ech.ch / http://www.ech.ch/ Fachgruppe XML-Standards: Hanspeter Salvisberg...»

«In the United States Court of Appeals For the Seventh Circuit No. 11-1989 JOHANA CECE, Petitioner, v. ERIC H. HOLDER, JR., Attorney General of the United States, Respondent. Petition for Review of an Order of the Board of Immigration Appeals. No. A096 158 857 ARGUED OCTOBER 5, 2011—DECIDED FEBRUARY 6, 2012 Before EASTERBROOK, Chief Judge, and MANION and ROVNER, Circuit Judges. MANION, Circuit Judge. Johana Cece, a citizen of Albania, petitions for review of a decision from the Board of...»

«EINFLUSS VON PLASMAEXPANDERN AUF ENDOTHELABHÄNGIGE, VASOAKTIVE FAKTOREN AN HERZKRANZGEFÄßEN VON SCHWEINEN MAITE ANN-KATRIN KLISA INAUGURAL-DISSERTATION zur Erlangung des Grades eines Dr. med. vet. beim Fachbereich Veterinärmedizin der Justus-Liebig-Universität Gießen édition scientifique VVB LAUFERSWEILER VERLAG Das Werk ist in allen seinen Teilen urheberrechtlich geschützt. Jede Verwertung ist ohne schriftliche Zustimmung des Autors oder des Verlages unzulässig. Das gilt insbesondere...»

«Russell: “On Denoting” DENOTING PHRASES Russell includes all kinds of quantified subject phrases (‘a man’, ‘every man’, ‘some man’ etc.) but his main interest is in definite descriptions: ‘the present King of England’, ‘the present King of France’. Curiously, Russell omits proper names, but he would count them as denoting phrases. Russell: a definite description functions grammatically in the same way as a proper name: as a denoting phrase that purports to uniquely pick...»

«School of Marketing GENC6003 Tourism: The Global Future Session 1 2007 Lecturer-in-charge Dr Roger March CONTENTS Lecturers and Contacts Details 3-4 Lecture Times and Location 4 Lecture Program 4 Course Description 5 Objectives of the course 5 Learning Outcomes 5 Course Requirements 5-6 Assessment, 6 Approach to Learning 6 Learning Support 7 Educational Development Unit 7 Other Sources of support 7-8 Academic Misconduct 8 Materials 8 Readings 8 References 8-9 Teaching Staff Lecturer in Charge...»

«See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/228499307 All Nitrogen or High Nitrogen Compounds as High Energy Density Materials Article · October 2004 READS 7 authors, including: Karl O Christe Ralf Haiges University of Southern California University of Southern California 558 PUBLICATIONS 7,475 CITATIONS 144 PUBLICATIONS 1,202 CITATIONS SEE PROFILE SEE PROFILE...»

«IF THE CAP FITS A COMEDIETTA IN ONE ACT BY MESSRS. N. H. HARRINGTON AND EDMUND YATES [MEMBERS OF THE DRAMATIC AUTHORS' SOCIETY.] AUTHORS OF A Night at Notting Hill—My Friend from Leatherhead—Double Duummy—Your Likeness One Shilling, &c., &c., THOMAS HAILES LACY, 89, STRAND, (Opposite Southampton Street, Covent Garden Market.) LONDON. IF THE CAP FITS— First produced at the Royal Princess's Theatre, June 13, 1859. CHARACTERS. CAPTAIN LYNCH Mr. W. LACY. of LIEUT. DALRYMPLE Mr. G. EVERETT....»

«Report on Ebla BST 550 Old Testament and the Ancient Near East Dr. Delamarter Jeffrey Chambers February 17, 2002 General Information Before 1960 archaeology had focused its efforts on Egypt, Mesopotamia, and Palestine. Little regard had been given to Syria. The presence of a great number of tells caused Professor Paolo Matthiae to begin excavation of the largest tell he found; Tell Mardikh. Tell Mardikh covers more than 140 acres and is 50 feet high. This tell is located in Northern Syria about...»

«MASARYK UNIVERSITY IN BRNO FACULTY OF EDUCATION Bachelor Thesis Brno 2011 Karel Ševčík MASARYK UNIVERSITY IN BRNO FACULTY OF EDUCATION Department of English Language and Literature Myles Horton and the Highlander Folk School Bachelor Thesis Brno 2011 Supervisor: Written by: Dr. Rita Chalmers Collins Karel Ševčík Bibliography Ševčík, Karel. Myles Horton and the Highlander Folk School. Brno: Masaryk University, Faculty of Education, Department of English Language and Literature, 2011. 45...»

«LETAYMIKLOS AZ ÓBUDAI SZENTHÁROMSÁG-SZOBORCSOPORT E téma azért aktuális, mert Óbudán, a Szentlélek téren újra fel akarják állítani az 1956-ban lebontott Szentháromság-szoborcsoportot. Már kutatásom kezdetén kitűnt, hogy egy idevágó tanulmány elkészí­ tését leginkább két tény indokol(hat)ja Egyrészt még soha senki nem írta meg e köztéri alkotás történe­ tét, illetve az eddig megjelent szórványos adatok közül jó néhány téves. Másrészt a lebontott...»

«Directorate-General for Research WORKING PAPER ABRIDGED MULTILINGUAL EDITION Wasser und Entwicklung DE in die Entwicklungsländern Water and development EN in the developing countries Agua y desarrollo ES en los países en vías de desarrollo L'eau et le développement FR dans les pays en développement Risorse idriche e sviluppo IT nei paesi in via di sviluppo Development Series DEVE 100 A XX The full study is only available in English (DEVE 100 EN). PUBLISHER: European Parliament L-2929...»

«Improving the Reliability of Commodity Operating Systems MICHAEL M. SWIFT, BRIAN N. BERSHAD, and HENRY M. LEVY University of Washington Despite decades of research in extensible operating system technology, extensions such as device drivers remain a significant cause of system failures. In Windows XP, for example, drivers account for 85% of recently reported failures. This paper describes Nooks, a reliability subsystem that seeks to greatly enhance OS reliability by isolating the OS from...»

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