Paul Young

NeurIPS Conference 2020 Conference Paper

Ensembling geophysical models with Bayesian Neural Networks

• Ushnish Sengupta
• Matt Amos
• Scott Hosking
• Carl Edward Rasmussen
• Matthew Juniper
• Paul Young

Ensembles of geophysical models improve projection accuracy and express uncertainties. We develop a novel data-driven ensembling strategy for combining geophysical models using Bayesian Neural Networks, which infers spatiotemporally varying model weights and bias while accounting for heteroscedastic uncertainties in the observations. This produces more accurate and uncertainty-aware projections without sacrificing interpretability. Applied to the prediction of total column ozone from an ensemble of 15 chemistry-climate models, we find that the Bayesian neural network ensemble (BayNNE) outperforms existing ensembling methods, achieving a 49. 4% reduction in RMSE for temporal extrapolation, and a 67. 4% reduction in RMSE for polar data voids, compared to a weighted mean. Uncertainty is also well-characterized, with 90. 6% of the data points in our extrapolation validation dataset lying within 2 standard deviations and 98. 5% within 3 standard deviations.

TCS Journal 1991 Journal Article

On sets polynomially enumerable by iteration

• Lane A. Hemachandra
• Albrecht Hoene
• Dirk Siefkes
• Paul Young

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ⪯p 1 si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are p 1 si-self-reducible are bi-enumerable. We also show that when the ⪯p 1 si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.

TCS Journal 1985 Journal Article

Reductions among polynomial isomorphism types

• Stephen R. Mahaney
• Paul Young

A set A is polynomial many-one reducible to a set B (A is Karp-reducible to B) if there is a polynomially computable function f such that, for all x, x ϵ A iff f(x) ϵ B. Arbitrary sets A and B are of the same polynomial many-one degree if each is polynomial many-one reducible to the other. A and B are (polynomially) isomorphic if the function f can be taken one-to-one, onto, and polynomially invertible. In classical recursive function theory, all many-one complete sets are recursively isomorphic. Berman and Hartmanis have observed that all known NP-complete sets are polynomially isomorphic, Berman and Hartmanis have observed that all known NP-complete sets are polynomially isomorphic, and have conjectured that all NP-complete sets (complete under Karp-reducibility) are isomorphic. In this paper we show that not just the complete degree, but every polynomial many-one degree consists either of a single isomorphism type or else contains infinitely many isomorphism types densely ordered under one-one, size-increasing, polynomially invertible reductions and also contains infinitely many isomorphisms types which are incomparable under one-one invertible reductions. In fact, we show that every countable partial ordering can be embedded in any such many-one degree. We also exhibit polynomial degrees which have infinitely many isomorphism types. No examples are known of degrees consisting of a single isomorphism type.

TCS Journal 1985 Journal Article

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP

• Deborah Joseph
• Paul Young

We present two results about witness functions for sets in NP and coNP. First, any set that has a polynomially computable function which witnesses that it is not in coNP must be at least NP-hard. It follows from this result that any set in NP-coNP that has a polynomially computable function which witnesses this fact must already be complete for NP. Second, if B is any set for which there is a polynomially computable function which witnesses that it is not complete for NP by witnessing that some fixed set in NP is not in P B, then B must already be in NP ⊃ coNP. Thus, for two sets in NP-coNP there are no polynomially computable functions which witness that one is not polynomially reducible to the other. In proving the first result we introduce the notion of a k-creative set and prove that all k-creative sets are NP-complete. Since these sets seem not to be all polynomially isomorphic, we counter the conjecture of Berman and Hartmanis that all NP-complete sets are isomorphic to SAT with our own conjecture that not all k-creative sets are isomorphic to SAT. The proofs we give are recursion-theoretic in style, but straightforward.

STOC Conference 1983 Conference Paper

Some Structural Properties of Polynomial Reducibilities and Sets in NP

• Paul Young

MFCS Conference 1981 Invited Paper

A Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmetic

• Deborah Joseph
• Paul Young

STOC Conference 1981 Conference Paper

Fast Programs for Initial Segments and Polynomial Time Computation in Weak Models of Arithmetic (Preliminary Abstract)

• Deborah Joseph
• Paul Young

STOC Conference 1980 Conference Paper

Independence Results in Computer Science? (Preliminary Version)

• Deborah Joseph
• Paul Young

Although there has been considerable additional work discussing limitations of formal proof techniques for Computer Science ([YO-73&77], [HAR-76], [HAR&HO-77], [HAJ-77&79], [GO-79]), these papers show only very general consequences of incompleteness: the stated results hold for all sufficiently powerful formal systems for Computer Science. Only the work of O'Donnell and of Lipton directly addresses the question of just how powerful formal axioms for Computer Science should be, and these two authors make rather radically different suggestions.

STOC Conference 1976 Conference Paper

Simple Gödel Numberings, Translations, and the P-Hierarchy

• Michael Machtey
• Paul Young

We study restricted classes of programming systems (Gödel numberings), where a programming system is in a given class if every programming system can be translated into it by functions in a given restricted class. For pairs of systems in various “natural” classes we give results on the existence of isomorphisms (one-to-one and onto translations) between them from the appropriate class of functions. Our results with the most computational significance concern polynomial time programming systems. We show that if P=NP then every two polynomial time programming systems are isomorphic via a polynomial time computable function. If [email protected] @@@NP this result points the way to the possible existence of “natural” but intractable computational problems concerning programming systems classified in terms of the polynomial time hierarchy. We also give results concerning the relationship between the complexity of certain important and commonly used properties of programming systems (such as effective composition of programs) and the complexity of translations into the systems.