FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 | 2 || 4 | 5 |   ...   | 16 |

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

-- [ Page 3 ] --

Obtaining tight bounds for H-Matching seems to be a challenging problem in general. As Theorem 1.6 shows in the case of cliques, the lower bound of O(k 2− ) implied by Theorem 1.7 is not always tight. We demonstrate that the upper bound of O(k |V (H)| ) is not always tight either. A simple argument shows that if H is a star of arbitrary size, then a kernel of size O(k 2 ) is possible, which is tight by Theorem 1.7. The examples of cliques and stars show that the exact bound on the kernel size of H-Matching for a particular H could be very far from the weak O(k |V (H)| ) upper bound or the weak O(k 2− ) lower bound (Theorem 1.7). Full understanding of this question seems to be a very challenging, yet very natural problem. The proofs of all packing-related results are in §3.5.

Techniques and Related Work At a high level our approach refines the framework developed by Bodlaender et al.

[BDFH09] to show that certain parameterized NP-hard problems are unlikely to have kernels of polynomial size. Harnik and Naor [HN06] realized the connection between their notion of lossy compression, kernelization, and PCPs for satisfiability of general Boolean formulas, and Fortnow and Santhanam [FS08] proved the connection with the hypothesis coNP ⊆ NP/poly in the superpolynomial setting. Several authors subsequently applied the framework to prove polynomial kernel lower bounds under this hypothesis [CFM07, BTY09, DLS09, FFL+ 09, KW10, KW09, KMW10].

We develop the first application of the framework in the polynomial setting, i.e., to problems that do have kernels of polynomial size, or more generally, oracle communication protocols of polynomial cost. Under the same hypothesis we show that problems like d-Sat, vertex cover, or set packing do not have protocols of polynomial cost of degree less than the best known. All known kernel lower bounds for fixed-parameter tractable problems use, at least implicitly, the following lemma as a proxy. The lemma follows

1. Introduction

along the lines of the proof of Fortnow and Santhanam [FS08], and we generalize it to the oracle communication model in §3.1.

Lemma 1.1 (OR Incompressibility Lemma).

For any NP-hard language L and polynomially bounded function t : N → N \ {0}, the problem ORt (L) does not have a compression of size O(t log t) unless coNP ⊆ NP/poly.

Here ORt (L) is the problem whose yes-instances are t-tuples of instances of L each of the same size s such that t = t(s) and at least one of the instances is a yes-instance of L. Under the assumption coNP ⊆ NP/poly, this lemma says that the problem ORt (L), seen as a parameterized problem with parameter s, does not have kernels of size O(t(s) log t(s)) even if we relax our notion of kernelization to compressions, in which the target language of the reduction may differ from the source language. We review how this theorem can be used to prove conditional polynomial kernel lower bounds for the k-path problem in §2.2.

Our main result, Theorem 1.2, deals with the vertex cover problem on d-uniform hypergraphs, or equivalently, with the clique problem on such graphs, parameterized by the number of vertices. Assuming the above incompressibility lemma, the proof of this result consists of a polynomial-time mapping reduction from OR(L) to the clique problem such that t-tuples of instances of size s are mapped to instances with few vertices n = n(s, t). Then any assumed kernelization of size O(nc ) for the clique problem can be combined with this reduction to give a compression of size O(nc ) for ORt (L).

As observed by Harnik and Naor [HN06], the disjoint union of the given hypergraphs provides a reduction from OR(L) to L if L is the clique problem itself. However, the number of vertices is n = s · t, so even if c = 1, the size of the compression for OR(L) is ω(t log t), which is too much for Lemma 1.1 to apply. As a critical piece in our proof, we present a reduction from OR(3-Sat) to clique that only needs n = s · t1/d vertices. The size of the combined compression for OR(3-Sat) then goes down to O(nc ) = O (s·t1/d )c, which is O(t log t) for some sufficiently large polynomial t(s) as long as c d.

In fact, we have two reductions for clique that yield these tight results: one is elementary and the other hinges on a graph packing that is based on high-density subsets of the integers without nontrivial arithmetic progressions of length three. For Theorem 1.7, we give a proof using the latter construction. After we developed the construction based on arithmetic progression free sets, we have learned about other applications of those sets in the theory of computing, including three-party communication protocols [CFL83], the asymptotically best known algorithm for matrix multiplication [CW90], the soundness analysis of graph tests for linearity [HW03], and lower bounds for property testing [AFKS00, Alo02, AS06, AS04, AKKR08, AS05]. The latter two applications as well as ours implicitly or explicitly rely on a connection due to Ruzsa and Szemerédi [RS78] between these subsets and dense three-partite graphs whose edges partition into triangles and that contain no other triangles. The graph packing we develop is most akin to a construction by Alon and Shapira [AS05] in the context of property testing. We refer to §4 for a more detailed discussion of the relationships.

We can generalize Lemma 1.1 to show that whenever ORt (L) has a low-cost protocol, the complement of L has short witnesses that can be verified efficiently with the help

1.2. Sparse Instances of Counting Problems

of a polynomial-size advice string, i.e., L ∈ NP/poly. We refer to this generalization as the Complementary Witness Lemma and we prove it in §3.1. It involves a refined analysis and generalization of the proof of Fortnow and Santhanam [FS08] that establishes the case where the protocol implements a mapping reduction to instances of bitlength bounded by some fixed polynomial in s. We analyze what happens for mapping reductions without the latter restriction and we observe that the argument generalizes to our oracle communication protocol setting. Our applications of Theorem 1.1 only use oracle communication protocols that implement mapping reductions or general reductions. For the results concerned with mapping reduction, Lemma 1.1 would suffice. However, the setting of oracle communication protocols is more natural and allows us to prove known results in a simpler way, as we discuss in §3.6.

1.2. Sparse Instances of Counting Problems

The permanent of a matrix and the Tutte polynomial of a graph are central topics in the study of counting algorithms. Originally defined in the combinatorics literature, they unify and


many enumeration problems, including immediate questions about graphs such as computing the number of perfect matchings, spanning trees, forests, colourings, certain flows and orientations, but also less obvious connections to other fields, such as link polynomials from knot theory, reliability polynomials from network theory, and (maybe most importantly) the Ising and Potts models from statistical physics.

From its definition (repeated in (1.1) below), the permanent of an n × n-matrix can be computed in O(n!n) time, and the Tutte polynomial (1.2) can be evaluated in time exponential in the number of edges. Both problems are famously #P-hard, which rules out the existence of polynomial-time algorithms under standard complexity-theoretic assumptions, but that does not mean that we have to resign ourselves to brute-force evaluation of the definition. In fact, Ryser’s famous formula [Rys63] computes the permanent with only exp(O(n)) arithmetic operations, and more recently, an algorithm with running time exp(O(n)) for n-vertex graphs has also been found [BHKK08] for the Tutte polynomial. Curiously, both of these algorithms are based on the inclusion–exclusion principle. In this thesis, we show that these algorithms cannot be significantly improved, by providing conditional lower bounds of exp(Ω(n)) for both problems.

It is clear that #P-hardness is not the right conceptual framework for such claims, as it is unable to distinguish between different types of super-polynomial time complexities. For example, the Tutte polynomial for planar graphs remains #P-hard, but can √ be computed in time exp(O( n)) [SIT95]. Therefore, we work under the Exponential Time Hypothesis (ETH), viz. the complexity theoretic assumption that deciding the satisfiability of 3-CNF formulas in n variables requires time exp(Ω(n)). More specifically, we introduce #ETH, a counting analogue of ETH which models the hypothesis that counting the satisfying assignments requires time exp(Ω(n)).

1. Introduction Computing the permanent The permanent of an n × n matrix A is defined as

–  –  –

where Sn is the set of permutations of {1,..., n}. This is similar to the determinant from linear algebra, det A = π sign(π) i Aiπ(i), the only difference is an easily computable sign for every summand. Both definitions involve a summation with n! terms, but admit much faster algorithms that are textbook material: The determinant can be computed in polynomial time using Gaussian elimination and the permanent can be computed in O(2n n) operations using Ryser’s formula.

Valiant’s celebrated #P-hardness result [Val79] for the permanent shows that no polynomial-time algorithm à la “Gaussian elimination for the permanent” can exist unless P = NP, and indeed unless P = P#P. Several unconditional lower bounds for the permanent in restricted models of computation are also known. [JS82] have shown that monotone arithmetic circuits need n(2n−1 − 1) multiplications to compute the permanent, a bound they can match with a variant of Laplace’s determinant expansion. [Raz09] has shown that multi-linear arithmetic formulas for the permanent require size exp(Ω(log2 n)). Ryser’s formula belongs to this class of formulas, but is much larger than the lower bound; no smaller construction is known. Intriguingly, the same lower bound holds for the determinant, where it is matched by a formula of size exp(O(log2 n)) due to [Ber84]. One of the consequences of this thesis is that Ryser’s formula is in some sense optimal under #ETH. In particular, no uniformly constructible, subexponential size formula such as Berkowitz’s can exist for the permanent unless #ETH fails.

A related topic is the expression of per A in terms of det f (A), where f (A) is a matrix of constants and entries from A and is typically much larger than A. This question has fascinated many mathematicians for a long time, see Agrawal’s survey [Agr06]; the best known bound on the dimension of f (A) is exp(O(n)) and it is conjectured that all such constructions require exponential size. In particular, it is an important open problem if a permanent of size n can be expressed as a determinant of size exp(O(log2 n)). We show that under #ETH, if such a matrix f (A) exists, computing f must take time exp(Ω(n)).

Computing the Tutte polynomial The Tutte polynomial, a bivariate polynomial associated with a given graph G = (V, E) with n vertices and m edges, is defined as

–  –  –

where k(A) denotes the number of connected components of the subgraph (V, A).

Despite their unified definition (1.2), the various computational problems given by T (G; x, y) for different points (x, y) differ widely in computational complexity, as well as in the methods used to find algorithms and lower bounds.

1.2. Sparse Instances of Counting Problems

For example, T (G; 1, 1) equals the number of spanning trees in G, which happens to admit a polynomial time algorithm, curiously again based on Gaussian elimination.

On the other hand, the best known algorithm for computing T (G; 2, 1), the number of forests, runs in exp(O(n)) time.

Computation of the Tutte polynomial has fascinated researchers in computer science and other fields for many decades. For example, the algorithms of Onsager and Fischer from the 1940s and 1960s for computing the so-called partition function for the planar Ising model are viewed as major successes of statistical physics and theoretical chemistry;

this corresponds to computing T (G; x, y) along the hyperbola (x − 1)(y − 1) = 2 for planar G. Many serious attempts were made to extend these results to other hyperbolas or graph classes, but “after a quarter of a century and absolutely no progress”, Feynman in 1972 observed that “the exact solution for three dimensions has not yet been found”.1 The failure of theoretical physics to “solve the Potts model” and sundry other questions implicit in the computational complexity of the Tutte polynomial were explained only with Valiant’s #P-hardness programme. After a number of papers, culminating in [JVW90], the polynomial-time complexity of exactly computing the Tutte polynomial at points (x, y) is now completely understood: it is #P-hard everywhere except at those points (x, y) where a polynomial-time algorithm is known; these points consist of the hyperbola (x − 1)(y − 1) = 1 as well as the four points (1, 1), (−1, −1), (0, −1), (−1, 0).

In this thesis, we show an exp(Ω(n)) lower bound to match the exp(O(n)) algorithm from [BHKK08], which holds under #ETH everywhere except for |y| = 1. In particular, √ this establishes a gap to the planar case, which admits an exp(O( n)) algorithm [SIT95].

Our hardness results apply (though not everywhere, and sometimes with a weaker bound) even if the graphs are sparse and simple. These classes are of particular interest because most of the graphs arising from applications in statistical mechanics arise from bond structures, which are sparse and simple.

It has been known since the 1970s [Law76] that graph 3-colouring can be solved in time exp(O(n)), and this is matched by an exp(Ω(n)) lower bound under ETH [IPZ01].

Since graph 3-colouring corresponds to evaluating T at (−2, 0), the exponential time complexity for T (G; −2, 0) was thereby already understood. In particular, computing T (G; x, y) for input G and (x, y) requires vertex-exponential time, an observation that is already made in [GHN06] without explicit reference to ETH.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 16 |

Similar works:

«editorial board ZEHRA AYHAN, Ph.D. Associate Professor Phone: +90 326-245 5624 Fax: +90 326-245 5832 Email: zayhan@mku.edu.tr, zehra.ayhan@gmail.com EDUCATION Ph.D. August 2000, Food Science and Technology, The Ohio State University, USA M.Sc. August 1996, Food Science and Technology, The Ohio State University, USA B.Sc. June 1991, Food Science and Technology, Ankara University, TURKEY WORK EXPERIENCE 2009-present. Department of Food Engineering, Mustafa Kemal University, Associate Professor...»

«AUSWIRKUNGEN DER SCHULDENBREMSE AUF DIE HAUSHALTE AUSGEWÄHLTER BUNDESLÄNDER UND IHRER GEMEINDEN Expertise im Auftrag von ver.di · von Dieter Vesper Bund+ Länder und Gemeinden AUSWIRKUNGEN DER SCHULDENBREMSE AUF DIE HAUSHALTE AUSGEWÄHLTER BUNDESLÄNDER UND IHRER GEMEINDEN Expertise im Auftrag von ver.di · von Dieter Vesper Bund+ Länder und Gemeinden Herausgeber: ver.di – Vereinte Dienstleistungsgewerkschaft, Paula-Thiede-Ufer 10, 10179 Berlin V.i.S.d.P. Achim Meerkamp, Mitglied des...»

«Virtual mentor and media structuralization theory Item type text; Dissertation-Reproduction (electronic) Authors Zhang, Dongsong Publisher The University of Arizona. Rights Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author. Downloaded 7-May-2016...»

«Современные методы и международный опыт Сохранения генофонда дикораСтущих раСтений Современные методы (на примере диких плодовых) и международный опыт Сохранения генофонда дикораСтущих раСтений (на примере диких плодовых) Программа развития ООН в Казахстане г. Астана,...»

«A qualitative evaluation of non-educational barriers to the elite professions June 2015 Dr Louise Ashley, Royal Holloway University of London Professor Jo Duberley, University of Birmingham Professor Hilary Sommerlad, University of Birmingham Professor Dora Scholarios, University of Strathclyde Social Mobility and Child Poverty Commission Sanctuary Buildings 20 Great Smith Street London SW1P 3BT contact@smcpcommission.gsi.gov.uk About the Commission The Social Mobility and Child Poverty...»

«Ligand Exchange Processes on Solvated Lithium Cations Den Naturwissenschaftlichen Fakultäten der Friedrich-Alexander-Universität Erlangen-Nürnberg zur Erlangung des Doktorgrades vorgelegt von Ewa Maria Pasgreta aus Więcbork (Polen) Als Dissertation genehmigt von den Naturwissenschaftlichen Fakultäten der Universität Erlangen-Nürnberg Tag der mündlichen Prüfung: 23. 3. 2007 Vorsitzender der Promotionskommission: Prof. Dr. Eberhard Bänsch Erstberichterstatter: Prof. Dr. Dr. h.c. mult....»

«SCHLUSSFOLGERUNGEN DES VORSITZES 1. Der Tagung des Europäischen Rates ging ein Exposé des Präsidenten des Europäischen Parlaments, Josep Borrell, voraus, an das sich ein Gedankenaustausch anschloss.2. Der Europäische Rat weist erneut darauf hin, wie wichtig die gemeinsamen europäischen Werte der Solidarität, der sozialen Gerechtigkeit und der Nachhaltigkeit als Grundlage für die Gestaltung der Unionspolitik sind. Sie bilden den Rahmen, in dem die in diesen Schlussfolgerungen enthaltenen...»

«Ergebnisdarstellung – SaarLernNetz –Lernende Region Saarland Planungsphase http://www.saarlernnetz.de/ Autoren: Dr. Josef Burgard, DFKI, Gesamtprojektleiter SaarLernNetz Wolfgang Vogt, BFW, Teilprojekt 1: Neugier auf Wissen Michael Röser, CJDe-Learning Center, Teilprojekt 2: Go2Live Karl Schiene, Steinbeis, Teilprojekt 3:TILL Erwin Irmisch, Bildungszentrum Kirkel, Teilprojekt 4 Christof Ecker, Arbeitskammer, Teilprojekt 5: ARGUS Patric Kany, CEB, Teilprojekt 6: Virtuelle Akademie Nico...»

«Christoph Revermann Peter Georgieff Simone Kimpeler Mediennutzung und eLearning in Schulen Sachstandsbericht zum Monitoring »eLearning« Dezember 2007 Arbeitsbericht Nr. 122 INHALT ZUSAMMENFASSUNG 5 I. EINLEITUNG 21 1. Thematischer Hintergrund 22 1.1 eLearning – Definition und Varianten 25 1.2 Pädagogisch-didaktische Konzepte 26 1.3 Neue Lernformen und Elemente von eLearning 28 2. Anliegen und Struktur des Berichts 30 3. Zusammenarbeit mit Gutachtern 31 II. DISKUSSIONSSTAND UND...»

«Isabelle Kelly Raubitschek 1914-1988 By P. Terrence Hopmann1 Isabelle Kelly Raubitschek was a scholar of classical Greek and Roman archaeology, whose career culminated as Associate Professor of Art at Stanford University. Her magnum opus was published posthumously in 1998. Entitled Isthmia, Vol. VII: The Metal Objects (1952-1989), it is an analysis of objects in bronze, iron, copper, gold, silver, and lead recovered from the Sanctuary of Poseidon at Isthmia. In this work, Professor Raubitschek...»

«KfW/ ZEW CO2 BarOmEtEr 2012 anreizwirkung des EU-Emissionshandels auf Unternehmen gering – Klimapolitische regulierung wenig relevant für Standortentscheidungen BAROMETER Herausgeber KfW Bankengruppe Palmengartenstraße 5-9 60325 frankfurt am main www.kfw.de Zentrum für Europäische Wirtschaftsforschung GmbH (ZEW) L 7, 1 68161 mannheim www.zew.de redaktion KfW Bankengruppe abteilung Volkswirtschaft karl-ludwig.brockmann@kfw.de 069 7431-3771 Zentrum für Europäische Wirtschaftsforschung...»

«soFid Sozialwissenschaftlicher Fachinformationsdienst 02/2005 Kommunikationswissenschaft: Massenkommunikation – Medien Sprache GESIS-IZ Bonn 2005 Sozialwissenschaftlicher Fachinformationsdienst soFid Kommunikationswissenschaft Massenkommunikation Medien Sprache Band 2005/2 bearbeitet von Hannelore Schott Mit einem Beitrag von Charlotte Dany Informationszentrum Sozialwissenschaften Bonn 2005 ISSN: 1431-1038 Herausgeber Informationszentrum Sozialwissenschaften der Arbeitsgemeinschaft...»

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