FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 || 3 | 4 |   ...   | 16 |

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

-- [ Page 2 ] --

The number of variables n forms a natural parameter for satisfiability. In the case of d-CNF formulas, n is effectively polynomially related to the size of the input, which makes the existence of kernels of polynomial size trivial. The quest for a small kernel is a relaxation of the quest for sparsification in polynomial time. Eliminating duplicate clauses yields a kernel of bitlength O(nd log n). Does satisfiability of n-variable d-CNF formulas have kernels of size O(nd− )?

Lossy Compression. Harnik and Naor [HN06] introduced a notion of compression with the goal of succinctly storing instances of computational problems for resolution in the future, where there may be more time and more computational power available. The compressed version need not be an instance of the original problem, and the original instance need not be recoverable from the compressed version. The only requirement is that the solution be preserved. In the case of decision problems this simply means the yes/no answer. In analogy to image compression one can think of the Harnik-Naor notion of compression as a “lossy compression”, where the only aspect of the scenery that is guaranteed not to be lost is the solution to the problem.

Harnik and Naor applied their notion to languages in NP and showed the relevance to problems in cryptography when the compression is measured as a function of the bitlength of the underlying witnesses. In the case of satisfiability the latter coincides with the number of variables of the formula. This way lossy compression becomes a relaxation of the notion of kernelization – we now want a polynomial-time mapping reduction to any problem, rather than to the original problem, such that the reduced instances have small bitlength as a function of n. For d-CNF formulas bitlength O(nd ) is trivially achievable – simply map to the characteristic vector that for each possible d-clause on n variables indicates whether it is present in the given formula. Can we lossily compress to instances of bitlength O(nd− )?

Probabilistically Checkable Proofs. A somewhat different question deals with the size of probabilistically checkable proofs (PCPs). A PCP for a language L is a randomized proof system in which the verifier only needs to read a constant number of bits of the proof in order to verify that a given input x belongs to L. Completeness requires that for every input x in L there exists a proof which the verifier accepts with probability one. Soundness requires that for any input x outside of L no proof can be accepted with probability above some constant threshold less than one. For satisfiability of Boolean formulas, Dinur [Din07] constructed PCPs of bitlength O(s · poly log s), where s denotes the size of the formula. For d-CNF formulas on n variables, Dinur’s construction yields PCPs of bitlength O(nd · poly log n). On the other hand, standard proofs only contain n bits. Do n-variable d-CNF formulas have PCPs of bitlength O(nd− )?

1. Introduction

Our Results for Satisfiability We give evidence that the answer to all four of the above questions is negative: If any answer is positive then coNP is in NP/poly. The latter is considered unlikely as it means the existence of a nonuniform polynomial-time proof system for tautologies, or equivalently, that coNP has polynomial-size nondeterministic circuits, and implies that the polynomial-time hierarchy collapses to its third level [Yap83].

We obtain those statements as corollaries to a more general result, in which we consider the following communication process to decide a language L.

Definition 1.1 (Oracle Communication Protocol). An oracle communication protocol for a language L is a communication protocol between two players. The first player is given the input x and has to run in time polynomial in the length of the input; the second player is computationally unbounded but is not given any part of x. At the end of the protocol the first player should be able to decide whether x ∈ L. The cost of the protocol is the number of bits of communication from the first player to the second player.

We often refer to the second player as the oracle. Note that the bits sent by the oracle do not contribute towards the cost. By default the players in an oracle communication protocol are deterministic, but one can consider variants in which one or both players are randomized, nondeterministic, etc.

Satisfiability of n-variable d-CNF formulas has a trivial protocol of cost O(nd ). The following result implies that there is no protocol of cost O(nd− ) unless the polynomialtime hierarchy collapses. In fact, the result even holds when the first player is conondeterministic, i.e., when the first player can have multiple valid moves to choose from in any given step, possibly leading to different conclusions about the satisfiability of a given input formula ϕ, but such that (i) if ϕ is satisfiable then every valid execution comes to that conclusion, and (ii) if ϕ is not satisfiable then at least one valid execution comes to that conclusion.

Theorem 1.1.

Let d ≥ 3 be an integer and a positive real. If coNP ⊆ NP/poly, there is no protocol of cost O(nd− ) to decide whether an n-variable d-CNF formula is satisfiable, even when the first player is conondeterministic.

The proof of this theorem and its corollaries is in §3.3. The corollaries about sparsification, kernelization, and lossy compression follow by considering deterministic singleround protocols in which the polynomial-time player acts as a mapping reduction, sends the reduced instance to the computationally unbounded player, and the latter answers this query as a membership oracle. The corollary about probabilistically checkable proofs follows by considering a similar single-round protocol in which the first player is conondeterministic. Note that Theorem 1.1 can handle more general reductions, in which multiple queries are made to the oracle over multiple rounds. The above corollaries can be strengthened correspondingly. In fact, Theorem 1.1 is morally even more general as it allows the oracle to play an active role that goes beyond answering queries from the polynomial-time player. We discuss this potential further in §3.6.

1.1. Hardness of Sparsification

Our Results for Covering Problems By reducibility the lower bounds from Theorem 1.1 carry over to other parameterized NP-complete problems, where the tightness depends on how the reduction affects the parameterization. In fact, we derive Theorem 1.1 from a similar result for the vertex cover problem on d-uniform hypergraphs.

Theorem 1.2.

Let d ≥ 2 be an integer and a positive real. If coNP ⊆ NP/poly, there is no protocol of cost O(nd− ) to decide whether a d-uniform hypergraph on n vertices has a vertex cover of at most k vertices, even when the first player is conondeterministic.

We prove this theorem in §3.2. The cases of Theorem 1.2 with d ≥ 3 are equivalent to the corresponding cases of Theorem 1.1. Note, though, that Theorem 1.2 also holds for d = 2, i.e., for standard graphs.

Similar to Theorem 1.1, Theorem 1.2 can be interpreted in terms of (graph) sparsification, kernelization, lossy compression, and probabilistically checkable proofs. Regarding kernelization, Theorem 1.2 has an interesting implication for the vertex cover problem parameterized by the size of the vertex cover – one of the prime examples of a parameterized problem that is NP-hard but fixed-parameter tractable. Kernelizations for this problem have received considerable attention. For standard graphs S. Buss [BG93] came up with a kernelization avant la lettre. He observed that any vertex of degree larger than k must be contained in any vertex cover of size k, should it exist. This gives rise to a kernelization with O(k 2 ) vertices and O(k 2 ) edges. Subsequently, several researchers tried to reduce the size of the kernel. Various approaches based on matching, linear programming, and crown reductions (see [GN07] for a survey) led to kernels with O(k) vertices, one of which we review in §2.1, but the resulting kernels are all dense. It remains open to find kernels with O(k 2− ) edges. Since k ≤ n, the case d = 2 of Theorem 1.2 implies that such kernels do not exist unless the polynomial-time hierarchy collapses.

In fact, a similar result holds for a wide class of covering-type problems known as vertex deletion problems. For a fixed graph property Π, the corresponding vertex deletion problem asks whether removing at most k vertices from a given graph G can yield a graph that satisfies Π. A host of well-studied specific problems can be cast as the vertex deletion problem corresponding to some graph property Π that is inherited by subgraphs.

Examples besides the vertex cover problem include the feedback vertex set problem and the bounded-degree deletion problem (see §3.4 for the definitions of these problems and for more examples).

If only finitely many graphs satisfy Π or if all graphs satisfy Π, the vertex deletion problem is trivially decidable in polynomial time. For all other graph properties Π that are inherited by subgraphs, Lewis and Yannakakis [LY80] showed that the problem is NP-hard. They did so by constructing a mapping reduction from the vertex cover problem. By improving their reduction such that it preserves the size of the deletion set up to a constant factor, we obtain the following result.

Theorem 1.3.

Let Π be a graph property that is inherited by subgraphs, and is satisfied by infinitely many but not all graphs. Let be a positive real. If coNP ⊆ NP/poly,

1. Introduction there is no protocol of cost O(k 2− ) for deciding whether a graph satisfying Π can be obtained from a given graph by removing at most k vertices, even when the first player is conondeterministic.

The proof is in §3.4. Theorem 1.3 implies that problems like feedback vertex set and bounded-degree deletion do not have kernels consisting of O(k 2− ) edges unless the polynomial-time hierarchy collapses. For both problems the result is tight in the sense that kernels with O(k 2 ) edges exist. For feedback vertex set we argue that a recent kernelization by Thomassé [Tho09] does the job; for bounded-degree deletion, kernels with O(k 2 ) edges were known to exist [FGMN09].

Our Results for Packing Problems The matching problem in d-uniform hypergraphs, d-Set Matching, is to decide whether a given hypergraph has a matching of size k, i.e., a set of k pairwise disjoint hyperedges.

Correspondingly, the Perfect d-Set Matching problem is to find a perfect matching, i.e., a matching with k = n/d where n is the number of vertices. Fellows et al. [FKN+ 08] show that d-Set Matching has kernels with O(k d ) hyperedges.

Theorem 1.4 ([FKN+ 08]).

The problem d-Set Matching has kernels with O(k d ) hyperedges.

In Appendix B, we sketch a straightforward but instructive proof of this fact using the sunflower lemma of Erdős and Rado [ER60]. We use our lower bound technology for oracle communication protocols to prove that the kernel size above is asymptotically optimal under the hypothesis coNP ⊆ NP/poly.

Theorem 1.5.

Let d ≥ 3 be an integer and a positive real. If coNP ⊆ NP/poly, there it no protocol of cost O(k d− ) for Perfect d-Set Matching.

A particularly well-studied special case of set matching is when the sets are certain fixed subgraphs (e.g., triangles, cliques, stars, etc.) of a given graph. We use the terminology of Yuster [Yus07], who surveys graph theoretical properties of such graph packing problems. Formally, an H-matching of size k in a graph G is a collection of k vertex-disjoint subgraphs of G that are isomorphic to H. The problem H-Matching is to find an H-matching of a given size in a given graph. Both problems are NP-complete whenever H contains a connected component with more than two vertices [KH78] and is in P otherwise.

The kernelization properties of graph packing problems received a lot of attention in the literature (e.g., [Mos09, FHR+ 04, PS04, FR09, WNFC10, MPS04]). H-Matching can be expressed as a d-Set Matching instance with O(k d ) edges (where d := |V (H)|) and therefore Theorem 1.4 implies a kernel of size O(k d ). In the particularly interesting special case when H is a clique Kd, we use a simple reduction to transfer the above theorem to obtain a lower bound for Kd -Matching.

Theorem 1.6.

Let d ≥ 4 be an integer and a positive real. If coNP ⊆ NP/poly, there it no protocol of cost O(k d−1− ) for Kd -Matching.

1.1. Hardness of Sparsification

An upper bound of size O(k d ) follows for Kd -Matching from Theorem 1.4. This does not quite match our conditional lower bounds of O(k d−1− ), and it is an interesting open problem to make the bounds tight.

The H-Factor problem is the restriction of H-Matching to the case k = n/d, i.e., the goal is to find an H-matching that involves all vertices. Unlike the case of matching d-sets, where we had the same bounds for Perfect d-Set Matching and dSet Matching, we cannot expect that the same bounds hold always for H-Matching and H-Factor. The reason is that for H-Factor there is a trivial O(k 2 ) upper bound on the kernel size for every graph H: an n-vertex instance has size O(n2 ) and we have k = Θ(n) by the definition of H-Factor. We show that this bound is tight for every NP-hard H-Factor problem. Thus, we cannot reduce H-Factor to sparse instances.

Theorem 1.7.

Let H be a connected graph with d ≥ 3 vertices and a positive real. If coNP ⊆ NP/poly, there it no protocol of cost O(k 2− ) for Kd -Factor.

Obviously, Theorem 1.7 gives a lower bound for the more general H-Matching problem.

In particular, it proves the missing d = 3 case in Theorem 1.6.

Pages:     | 1 || 3 | 4 |   ...   | 16 |

Similar works:

«CURRICULUM VITAE William O. Okelo-Odongo, Ph.D., M.Sc., B.Sc. Birth: 31 January 1953. Kisumu District, Kenya Citizenship: Kenyan Current Appointment: Associate Professor in Computer Science, University of Nairobi Primary and Secondary Education: Standards 1 to 5: Mariwa Primary School, Kisumu District 1960 to 1964. Standards 6 and 7: St. Mary's School, Nairobi, Kenya, 1965 to 1966. Certificate of Primary Education awarded in December 1966. Form 1 to 4: St. Mary's School, Nairobi, Kenya., Jan...»

«BlindAid: An Electronic Travel Aid for the Blind Sandra Mau, Nik A. Melchior, Maxim Makatchev, Aaron Steinfeld CMU-RI-TR-07-39 smau@andrew.cmu.edu, melchior@cmu.edu, maxi@cmu.edu, steinfeld@cmu.edu The Robotics Institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 May 2008 Copyright c 2008 by Sandra Mau, Nik A. Melchior, Maxim Makatchev, Aaron Steinfeld. All rights reserved. Contents 1 Introduction 2 2 Motivation 3 3 Related Work 4 3.1 Interface.....................»

«1st July, 2010 Dear Members, We are loosing our forest cover at an alarming rate. The green patches we saw a few years back have now totally disappeared. Mumbai has a green lung or a city forest which is the Sanjay Gandhi National Park, Borivali. But the forest is loosing its green cover at an alarming rate, due to the encroachers and timber mafia. Richard st. Barbe Baker, founder of the “Man of the Trees “, during his last visit in 1981 warned the citizens of Mumbai that unless we protect...»

«University of Pittsburgh Department of Linguistics Graduate Student Handbook Revision 2.1 1.0 Purpose and scope This handbook is a collection of all department-level requirements, policies and procedures governing graduate study in the University of Pittsburgh Department of Linguistics. Full version numbers have been approved by the full faculty of the department, and minor revisions made by the Director of Graduate Study will be single decimals. Other important information is listed on the...»

«  Case Study #10-002 JetBlue: Bringing Humanity Back to Air Travel By Susan Fournier and Concetta Rini “It is hard to remember such a popular American company undergoing such a spectacular crisis.”i -Brian Williams, NBC Nightly News on February 19th, 2007 On February 14, 2007, a Northeastern ice storm left more than 1,000 JetBlue passengers stranded in nine aircraft for up to 10 hours on the tarmac at New York’s John F. Kennedy airport. Over the next five days, which included the...»

«Visual Odometry and Mapping for Autonomous Flight Using an RGB-D Camera Albert S. Huang, Abraham Bachrach, Peter Henry, Michael Krainin, Daniel Maturana, Dieter Fox, Nicholas Roy Abstract RGB-D cameras provide both a color image and per-pixel depth estimates. The richness of their data and the recent development of low-cost sensors have combined to present an attractive opportunity for mobile robotics research. In this paper, we describe a system for visual odometry and mapping using an RGB-D...»

«UNIVERSITY OF HELSINKI FACULTY OF BEHAVIOURAL SCIENCES Yuri Lapshin COLLECTIVE AGENCY FORMATION THROUGH THE RENEWAL OF SCHOOL ACTIVITY A Change Laboratory Interventional Study CRADLE Center for Research on Activity, Development and Learning Working papers 4/2013 University of Helsinki Center for Research on Activity, Development and Learning – CRADLE Working papers 4/2013 Yuri Lapshin COLLECTIVE AGENCY FORMATION THROUGH THE RENEWAL OF SCHOOL ACTIVITY A Change Laboratory Interventional Study...»

«CANADIAN PEACE RESEARCH ASSOCIATION (CPRA) 2015 CONFERENCE AND ANNUAL GENERAL COUNCIL MEETING 3-5 JUNE, 2015 UNIVERSITY OF OTTAWA, OTTAWA, ONTARIO, CANADA VENUE: JACKTURCOT UCU/205 [CENTRE UNIVERSTAIRE JOCK, MAIN CAMPUS, UNIVERSITY OF OTTAWA, ROOM #205, 2ND FLOOR] Welcome to the 2015 conference of the Canadian Peace Research Association (CPRA)a thoughtprovoking event, advancing research and discourse in the vast field of Peace Studies. We hope that you will enjoy and contribute to the...»

«Looking at the Executive Power through the High Court’s New Spectacles Gabrielle Appleby ∗ and Stephen McDonald † Abstract Federation heralded a new constitutional order in Australia. The new Constitution carefully divided legislative power between the two levels of government, but left the division of executive power between them unclear. Since Federation, it had generally been accepted, and reflected in the Commonwealth’s policies and conduct, that the Commonwealth executive power...»

«Exchange of Nutrients and Oxygen between Sediments and Water Column: the Role of the Benthic Boundary Layer Dissertation zur Erlangung des Doktorgrades der Naturwissenschaften dem Fachbereich Geowissenschaften der Universität Bremen vorgelegt von Moritz Holtappels Bremen, August 2009 Die vorliegende Arbeit wurde in der Zeit von Dezember 2005 bis August 2009 am MaxPlanck-Institut für marine Mikrobiologie in Bremen angefertigt.Gutachter: Prof. Dr. Bo Barker Jørgensen Prof. Dr. Michael...»

«Fellow Believers! The Minnesota South District of the Lutheran Church-Missouri Synod met in convention on June 18-20. Gary Anderson and I represented St. Peter at this convention. The Theme of this 77th Convention was On our way.Rejoicing. (Acts 8:39). This verse speaks of the Ethiopian Eunuch's joy as Philip shared the Gospel and baptized him on his way back home from a journey to Jerusalem. Wow! As he went forth, he would bear witness to the power of Jesus.and he did so rejoicing on his...»

«SECURITIES AND EXCHANGE COMMISSION (Release No. 34-77489; File No. SR-ISE-2016-08) March 31, 2016 Self-Regulatory Organizations; International Securities Exchange, LLC; Notice of Filing of Proposed Rule Change Related to Market Wide Risk Protection Pursuant to Section 19(b)(1) of the Securities Exchange Act of 1934 (“Act”), 1 and Rule 19b-4 thereunder, 2 notice is hereby given that, on March 17, 2016, the International Securities Exchange, LLC (the “Exchange” or “ISE”) filed with...»

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