An official website of the United States government
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that Few P ⊆ ⊕P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappiness”) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all\((\mathcal {O}(1) + \log \log n)\)-ambiguity NP sets are in the restricted counting class RCPRIMES.
more »
« less
Large prime gaps and progressions with few primes
We show that the existence of arithmetic progressions with few primes, with a quantitative bound on ''few'', implies the existence of larger gaps between primes less than x than is currently known unconditionally. In particular, we derive this conclusion if there are certain types of exceptional zeros of Dirichlet L-functions.
more »
« less
- Award ID(s):
- 1802139
- PAR ID:
- 10338321
- Editor(s):
- Alessandro Zaccagnini
- Date Published:
- Journal Name:
- Rivista di matematica della Università di Parma
- Volume:
- 12
- Issue:
- 1
- ISSN:
- 0035-6298
- Page Range / eLocation ID:
- 41-47
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕P (and thus that FewP ⊆ ⊕P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappy”-ness) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES .more » « less
-
Elkins, Christopher A. (Ed.)ABSTRACT Monitoring the prevalence of SARS-CoV-2 variants is necessary to make informed public health decisions during the COVID-19 pandemic. PCR assays have received global attention, facilitating a rapid understanding of variant dynamics because they are more accessible and scalable than genome sequencing. However, as PCR assays target only a few mutations, their accuracy could be reduced when these mutations are not exclusive to the target variants. Here we introduce PRIMES, an algorithm that evaluates the sensitivity and specificity of SARS-CoV-2 variant-specific PCR assays across different geographical regions by incorporating sequences deposited in the GISAID database. Using PRIMES, we determined that the accuracy of several PCR assays decreased when applied beyond the geographic scope of the study in which the assays were developed. Subsequently, we used this tool to design Alpha and Delta variant-specific PCR assays for samples from Illinois, USA. In silico analysis using PRIMES determined the sensitivity/specificity to be 0.99/0.99 for the Alpha variant-specific PCR assay and 0.98/1.00 for the Delta variant-specific PCR assay in Illinois, respectively. We applied these two variant-specific PCR assays to six local sewage samples and determined the dominant SARS-CoV-2 variant of either the wild type, the Alpha variant, or the Delta variant. Using next-generation sequencing (NGS) of the spike (S) gene amplicons of the Delta variant-dominant samples, we found six mutations exclusive to the Delta variant (S:T19R, S:Δ156/157, S:L452R, S:T478K, S:P681R, and S:D950N). The consistency between the variant-specific PCR assays and the NGS results supports the applicability of PRIMES. IMPORTANCE Monitoring the introduction and prevalence of variants of concern (VOCs) and variants of interest (VOIs) in a community can help the local authorities make informed public health decisions. PCR assays can be designed to keep track of SARS-CoV-2 variants by measuring unique mutation markers that are exclusive to the target variants. However, the mutation markers may not be exclusive to the target variants because of regional and temporal differences in variant dynamics. We introduce PRIMES, an algorithm that enables the design of reliable PCR assays for variant detection. Because PCR is more accessible, scalable, and robust for sewage samples than sequencing technology, our findings will contribute to improving global SARS-CoV-2 variant surveillance.more » « less
-
We propose that emotional priming may be an effective approach to scaffold the creation of rich stories. There are relatively few emotion-based approaches to support users to create, instead of consume, rich stories. Emotional priming is the technique of using emotion- related stimuli to affect human’s executive control and affective processing. It has been researched mostly in terms of human’s behaviors and decision making. We conducted a within-subjects study with 12 participants to investigate the effects of emotional priming induced through an interactive application on storytelling quality. Two conditions of priming were compared to a baseline condition of no priming. In the first condition, the application primes participants by having asking them to perceive and recognize varying emotional stimuli (perception-based priming). In the second condition, the application primes participants by having them produce varying emotional facial expressions (production- based priming). Analyses show that emotional priming resulted in richer storytelling than no emotional priming, and that the production-based emotional priming condition resulted in statistically richer stories being told by participants. We discuss the possibility of integrating interactive emotional priming into storytelling applications.more » « less
-
Abstract We develop an analog for shifted primes of the Kubilius model of prime factors of integers. We prove a total variation distance estimate for the difference between the model and actual prime factors of shifted primes, and apply it to show that the prime factors of shifted primes in disjoint sets behave like independent Poisson variables. As a consequence, we establish a transference principle between the anatomy of random integers $$\leqslant x$$ and of random shifted primes p+a with $$p\leqslant x$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
