Author name cluster

Stephen A. Fenner

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.

6 papers

2 author rows

STOC Conference 2016 Conference Paper

Bipartite perfect matching is in quasi-NC

Stephen A. Fenner
Rohit Gurjar
Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi- NC 2 . That is, it has uniform circuits of quasi-polynomial size n O (log n ) , and O (log 2 n ) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Details

I&C Journal 2013 Journal Article

Functions that preserve p-randomness

Stephen A. Fenner

We show that polynomial-time randomness (p-randomness) is preserved under a variety of familiar operations, including addition and multiplication by a nonzero polynomial-time computable real number. These results follow from a general theorem: If I ⊆ R is an open interval, f: I → R is a function, and r ∈ I is p-random, then f ( r ) is p-random provided 1. f is p-computable on the dyadic rational points in I, and 2. f varies sufficiently at r, i. e. , there exists a real constant C > 0 such that either ( ∀ x ∈ I − { r } ) [ f ( x ) − f ( r ) x − r ⩾ C ] or ( ∀ x ∈ I − { r } ) [ f ( x ) − f ( r ) x − r ⩽ − C ]. Our theorem implies in particular that any analytic function about a p-computable point whose power series has uniformly p-computable coefficients preserves p-randomness in its open interval of absolute convergence. Such functions include all the familiar functions from first-year calculus.

Details DOI

I&C Journal 2005 Journal Article

Weakly useful sequences

Stephen A. Fenner
Jack H. Lutz
Elvira Mayordomo
Patrick Reardon

An infinite binary sequence x is defined to be (i) strongly useful if there is a computable time bound within which every decidable sequence is Turing reducible to x; and (ii) weakly useful if there is a computable time bound within which all the sequences in a non-measure 0 subset of the set of decidable sequences are Turing reducible to x. Juedes, Lathrop, and Lutz [Theorectical Computer Science 132 (1994) 37] proved that every weakly useful sequence is strongly deep in the sense of Bennett [The Universal Turing Machine: A Half-Century Survey, 1988, 227] and asked whether there are sequences that are weakly useful but not strongly useful. The present paper answers this question affirmatively. The proof is a direct construction that combines the martingale diagonalization technique of Lutz [SIAM Journal on Computing 24 (1995) 1170] with a new technique, namely, the construction of a sequence that is “computably deep” with respect to an arbitrary, given uniform reducibility. The abundance of such computably deep sequences is also proven and used to show that every weakly useful sequence is computably deep with respect to every uniform reducibility.

Details DOI

I&C Journal 2003 Journal Article

Inverting onto functions

Stephen A. Fenner
Lance Fortnow
Ashish V. Naik
John D. Rogers

We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: • In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. • Every total multivalued nondeterministic function has a polynomial-time computable refinement. • In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. • In polynomial time, one can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments. We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse.

Details DOI

FOCS Conference 1992 Conference Paper

The Isomorphism Conjecture Holds Relative to an Oracle

Stephen A. Fenner
Lance Fortnow
Stuart A. Kurtz

The authors introduce symmetric perfect generic sets. these sets vary from the usual generic sets by allowing limited infinite encoding into the oracle. They then show that the Berman-Hartmanis (1977) isomorphism conjecture holds relative to any sp-generic oracle, i. e. , for any symmetric perfect generic set A, all NP/sup A/-complete sets are polynomial-time isomorphic relative to A. As part of the proof that the isomorphism conjecture holds relative to symmetric perfect generic sets they also show that P/sup A/=FewP/sup A/ for any symmetric perfect generic/sup /A. >

Details

FOCS Conference 1989 Conference Paper

Every Polynomial-Time 1-Degree Collapses iff P=PSPACE

Stephen A. Fenner
Stuart A. Kurtz
James S. Royer

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that for all x, x in A if and only if f(x) in B. Two sets are 1-equivalent if each is m-reducible to the other by one-one reductions; p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. It is proved that the following statements are equivalent: (1) P=PSPACE. (2) Every two 1-equivalent sets are p-isomorphic. (3) Every two p-invertible equivalent sets are p-isomorphic. >

Details