research-article

Reproducibility and pseudo-determinism in log-space

Authors:

Ofer Grossman,

Yang P. LiuAuthors Info & Claims

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 606 - 620

Published: 06 January 2019 Publication History

Get Access

Abstract

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits may result in a new (and potentially different) output.

We show that every problem in search-RL has a randomized log-space algorithm where the output can be reproduced. Specifically, we show that for every problem in search-RL, there are a pair of log-space randomized algorithms A and B where for every input x, A will output some string t_x of size O(log n), such that B when running on (x, t_x) will be pseudo-deterministic: that is, running B multiple times on the same input (x, t_x) will result in the same output on all executions with high probability. Thus, by storing only O(log n) bits in memory, it is possible to reproduce the output of a randomized log-space algorithm.

An algorithm is reproducible without storing any bits in memory (i.e., |t_x| = 0) if and only if it is pseudo-deterministic. We show pseudo-deterministic algorithms for finding paths in undirected graphs and Eulerian graphs using logarithmic space. Our algorithms are substantially faster than the best known deterministic algorithms for finding paths in such graphs in log-space.

The algorithm for search-RL has the additional property that its output, when viewed as a random variable depending on the randomness used by the algorithm, has entropy O(log n).

References

[1]

Romas Aleliunas, Richard M Karp, Richard J Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Foundations of Computer Science, 1979., 20th Annual Symposium on, pages 218--223. IEEE, 1979.

Digital Library

Google Scholar

[2]

Anna Gál and Avi Wigderson. Boolean complexity classes vs. their arithmetic analogs. Random Structures and Algorithms, 9(1--2):99--111, 1996.

Digital Library

Google Scholar

[3]

Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 18, page 136, 2011.

Google Scholar

[4]

Oded Goldreich, Shafi Goldwasser, and Dana Ron. On the possibilities and limitations of pseudodeterministic algorithms. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 127--138. ACM, 2013.

Digital Library

Google Scholar

[5]

Shafi Goldwasser and Ofer Grossman. Perfect bipartite matching in pseudo-deterministic RNC. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 208, 2015.

Google Scholar

[6]

Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-deterministic proofs. arXiv preprint arXiv:1706.04641, 2017.

Google Scholar

[7]

Ofer Grossman. Finding primitive roots pseudo-deterministically. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 207, 2015.

Google Scholar

[8]

Dhiraj Holden. A note on unconditional subexponential-time pseudo-deterministic algorithms for BPP search problems. arXiv preprint arXiv:1707.05808, 2017.

Google Scholar

[9]

Igor C Oliveira and Rahul Santhanam. Pseudo-deterministic constructions in subexponential time. arXiv preprint arXiv:1612.01817, 2016.

Google Scholar

[10]

Igor C Oliveira and Rahul Santhanam. Pseudo-derandomizing learning and approximation. In LIPIcs-Leibniz International Proceedings in Informatics, volume 116. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

Google Scholar

[11]

Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):17, 2008.

Digital Library

Google Scholar

[12]

Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 457--466. ACM, 2006.

Digital Library

Google Scholar

[13]

Klaus Reinhardt and Eric Allender. Making non-determinism unambiguous. SIAM Journal on Computing, 29(4):1118--1131, 2000.

Digital Library

Google Scholar

[14]

Michael Saks and Shiyu Zhou. BPHSPACE(S) ⊆ DSPACE(S<sup>3/2</sup>). Journal of Computer and System Sciences, 58(2):376--403, 1999.

Digital Library

Google Scholar

Cited By

View all

Goldwasser SImpagliazzo RPitassi TSanthanam R(2021)On the pseudo-deterministic query complexity of NP search problemsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.36Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.36

Reproducibility and pseudo-determinism in log-space

Recommendations

An O(log n log log n) space algorithm for undirected st-connectivity
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

We present a deterministic O(log n log log n) space algorithm for undirected st-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam [6] and uses the universal exploration sequences for trees constructed by Koucký [13]. Our ...
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space
FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science

We present a randomized algorithm sorting n integers in 0(n\sqrt {\log \log n}) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. from STOC'95. As an immediate consequence, if the integers are bounded by ...
Undirected connectivity in log-space

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log^4/3(⋅) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2019

2993 pages

Program Chair:
Timothy M. Chan
University of Illinois at Urbana-Champaign

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2019

Check for updates

Qualifiers

Research-article

Conference

SODA '19

Sponsor:

SODA '19: Symposium on Discrete Algorithms

January 6 - 9, 2019

California, San Diego

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
40
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Goldwasser SImpagliazzo RPitassi TSanthanam R(2021)On the pseudo-deterministic query complexity of NP search problemsProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.36Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.36

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

An O(log n log log n) space algorithm for undirected st-connectivity

Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space

Undirected connectivity in log-space