Author name cluster

David W. Juedes

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

MFCS Conference 2004 Conference Paper

A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs

Henning Fernau
David W. Juedes

Abstract This paper revisits design and analysis techniques for fixed parameter algorithms for Planar Dominating Set and other problems on planar structures. As our main result, we use new geometric arguments concerning treewidth-based algorithms to show that determining whether a planar graph G has a dominating set of size k can be solved in \(O(2^{16. 4715 \sqrt{k}}+ n^3)\) steps. This result improves on the best known treewidth-based algorithm by Kanj and Perkovič that runs in time \(O(2^{27\sqrt{k}}n)\). Our main result nearly matches the new branchwidth-based algorithm for Planar Dominating Set by Fomin and Thilikos that runs in time \(O(2^{15. 13 \sqrt{k}}k +n^3)\). Algorithms for other problems on planar structures are explored. In particular, we show that Planar Red/Blue Dominating Set can be solved in time \(O(2^{24. 551 \sqrt{k}}n)\). This leads to the main results, namely, that faster parameterized algorithms can be obtained for a variety of problems that can be described by planar boolean formulae. This gives the best-known parameterized algorithms for Planar Vertex Cover, Planar Edge Dominating Set, and Face Cover.

Details

I&C Journal 1996 Journal Article

Completeness and Weak Completeness under Polynomial-Size Circuits

David W. Juedes
Jack H. Lutz

This paper investigates the distribution and nonuniform complexity of problems that are complete or weakly complete for ESPACE under nonuniform reductions that are computed by polynomial-size circuits (P/Poly-Turing reductions and P/Poly-many–one reductions). A tight, exponential lower bound on the space-bounded Kolmogorov complexities of weakly P/Poly-Turing-complete problems is established. A Small Span Theorem for P/Poly-Turing reductions in ESPACE is proven and used to show thateveryP/Poly-Turing degree—including the complete degree—has measure 0 in ESPACE. (In contrast, it is known that almost every element of ESPACE is weakly P-many–one complete.) Every weakly P/Poly-many–one-complete problem is shown to have a dense, exponential, nonuniform complexity core. More importantly, the P/Poly-many–one-complete problems are shown to beunusually simpleelements of ESPACE, in the sense that they obey nontrivialupperbounds on nonuniform complexity (size of nonuniform complexity cores and space-bounded Kolmogorov complexity) that are violated by almost every element of ESPACE.

Details DOI

TCS Journal 1995 Journal Article

Weak completeness in E and E2

David W. Juedes
Jack H. Lutz

The notions of weak ⩽m P-completeness for the complexity classes E = DTIME(2linear) and E2 = DTIME(2polynomial) are compared. An element C of one of these classes is weakly ⩽m P- complete for the class if the set Pm(C), consisting of all languages A ⩽m P C, does not have measure 0 in the class. The following two results are proven. 1. (i)|Every problem that is weakly ⩽m P-complete for E is weakly ⩽m P-complete for E2. 2. (ii)|There is a problem in E that is weakly ⩽m P-complete for E2, but not for E.

Details DOI

TCS Journal 1994 Journal Article

Computational depth and reducibility

David W. Juedes
James I. Lathrop
Jack H. Lutz

This paper reviews and investigates Bennett's notions of strong and weak computational depth (also called logical depth) for infinite binary sequences. Roughly, an infinite binary sequence x is defined to be weakly useful if every element of nonnegligible set of decidable sequences is reducible to x in recursively bounded time. It is shown that every weakly useful sequence is strongly deep. This result (which generalizes Bennett's observation that the halting problem is strongly deep) implies that every high Turing degree contains strongly deep sequences. It is also shown that, in the sense of Baire category, almost every infinite binary sequence is weakly deep, but not strongly deep.

Details DOI

FOCS Conference 1993 Conference Paper

The Complexity and Distribution of Hard Problems (Extended Abstract)

David W. Juedes
Jack H. Lutz

Measure-theoretic aspects of the /spl les//sub m//sup P/-reducibility structure of exponential time complexity classes E=DTIME(2/sup linear/) and E/sub 2/=DTIME(2/sup polynomial/) are investigated. Particular attention is given to the complexity (measured by the size of complexity cores) and distribution (abundance in the sense of measure) of languages that are /spl les//sub m//sup P/-hard for E and other complexity classes. Tight upper and lower bounds on the size of complexity cores of hard languages are derived. The upper bounds say that the /spl les//sub m//sup P/-hard languages for E are unusually simple in, the sense that they have smaller complexity cores than most languages in E. It follows that the /spl les//sub m//sup P/-complete languages for E form a measure 0 subset of E (and similarly in E/sub 2/). This latter fact is seen to be a special case of a more general theorem, namely, that every /spl les//sub m//sup P/-degree (e. g. the degree of all /spl les//sub m//sup P/-complete languages for NP) has measure 0 in E and in E/sub 2/. >

Details