The Library
Pseudodeterministic lagorithms and the structure of probabilistic time
Tools
Tools
Tools
Lu, Zhen Jian, Oliveira, Igor C. and Santhanam, Rahul (2021) Pseudodeterministic lagorithms and the structure of probabilistic time. In: STOC 2021: 53rd Annual ACM Symposium on Theory of Computing, Virtual conference, 21-25 Jun 2021. Published in: STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing pp. 303-316. ISBN 9781450380539. doi:10.1145/3406325.3451085
|
PDF
WRAP-Pseudodeterministic-algorithms-structure-probabilistic-time-2021.pdf - Accepted Version - Requires a PDF viewer. Download (695Kb) | Preview |
Official URL: https://doi.org/10.1145/3406325.3451085
Abstract
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.
A new pseudorandom generator and its consequences. We build on techniques developed to prove hierarchy theorems for probabilistic time with advice (Fortnow and Santhanam, FOCS 2004) to construct the first unconditional pseudorandom generator of polynomial stretch computable in pseudodeterministic polynomial time (with one bit of advice) that is secure infinitely often against polynomial-time computations. As an application of this construction, we obtain new results about the complexity of generating and representing prime numbers. For instance, we show unconditionally for each ε > 0 that infinitely many primes pn have a succinct representation in the following sense: there is a fixed probabilistic polynomial time algorithm that generates pn with high probability from its succinct representation of size O(|pn|ε). This offers an exponential improvement over the running time of previous results, and shows that infinitely many primes have succinct and efficient representations.
Structural results for probabilistic time from pseudodeterministic algorithms. Oliveira and Santhanam (STOC 2017) established unconditionally that there is a pseudodeterministic algorithm for the Circuit Acceptance Probability Problem (CAPP) that runs in sub-exponential time and is correct with high probability over any samplable distribution on circuits on infinitely many input lengths. We show that improving this running time or obtaining a result that holds for every large input length would imply new time hierarchy theorems for probabilistic time. In addition, we prove that a worst-case polynomial-time pseudodeterministic algorithm for CAPP would imply that BPP has complete problems.
Equivalence between pseudodeterministic constructions and hierarchies. We establish an equivalence between a certain explicit pseudodeterministic construction problem and the existence of strong hierarchy theorems for probabilistic time. More precisely, we show that pseudodeterministically constructing in exponential time strings of large rKt complexity (Oliveira, ICALP 2019) is possible if and only if for every constructive function T(n) ≤ exp(o(exp(n))) we have BPTIME[poly(T)] ⊈ i.o.BPTIME[T]/logT.
More generally, these results suggest new approaches for designing pseudodeterministic algorithms for search problems and for unveiling the structure of probabilistic time.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Computer algorithms, Computer programming | ||||||
| Journal or Publication Title: | STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | ||||||
| Publisher: | ACM | ||||||
| ISBN: | 9781450380539 | ||||||
| Official Date: | 15 June 2021 | ||||||
| Dates: |
|
||||||
| Page Range: | pp. 303-316 | ||||||
| DOI: | 10.1145/3406325.3451085 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Reuse Statement (publisher, data, author rights): | "© ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 303-316 http://doi.acm.org/10.1145/3406325.3451085 | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 5 May 2021 | ||||||
| Date of first compliant Open Access: | 31 August 2021 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Is Part Of: | 1 | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | STOC 2021: 53rd Annual ACM Symposium on Theory of Computing | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Virtual conference | ||||||
| Date(s) of Event: | 21-25 Jun 2021 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
