Pseudo-determinism
A curious property of randomized algorithms for search problems is that on different executions on the same input, the algorithm may return different outputs due to differences in the internal randomness used by the algorithm. We would like to understand how we can construct randomized algorithms wh...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151209 |
| _version_ | 1826196477291003904 |
|---|---|
| author | Grossman, Ofer |
| author2 | Goldwasser, Shafi |
| author_facet | Goldwasser, Shafi Grossman, Ofer |
| author_sort | Grossman, Ofer |
| collection | MIT |
| description | A curious property of randomized algorithms for search problems is that on different executions on the same input, the algorithm may return different outputs due to differences in the internal randomness used by the algorithm. We would like to understand how we can construct randomized algorithms which while still using the power of randomness can ensure that when run multiple time on the same input, with high probability result in the same output on each of the executions.
We first show a pseudo-deterministic NC algorithm for finding matchings in bipartite graphs. As a corollary, we also show a pseudo-deterministic NC algorithm for constructing DFS trees in graphs.
We then show a reproducible algorithm for problems in search-RL. That is, we show an algorithm for problems in search-RL such that the output depends only on 𝑂(log 𝑛) many random bits used by the algorithm. We also show a pseudo-deterministic log-space low time algorithm for finding paths in undirected graphs. The algorithm is much faster than deterministic logspace algorithms for the problem.
Next, we investigate pseudo-determinism in the context of streaming algorithms. We show both lower and upper bounds for some classic streaming problems. Most notably, we show that the problem of approximate counting in a stream (for which the well known algorithm of Morris gives a 𝑂(log log 𝑛) space algorithm), has no pseudo-deterministic algorithms using space 𝑜(log 𝑛).
Finally, we examine an extension of pseudo-determinism to the context of interactive proofs. |
| first_indexed | 2024-09-23T10:27:34Z |
| format | Thesis |
| id | mit-1721.1/151209 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:27:34Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1512092023-08-01T04:03:48Z Pseudo-determinism Grossman, Ofer Goldwasser, Shafi Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science A curious property of randomized algorithms for search problems is that on different executions on the same input, the algorithm may return different outputs due to differences in the internal randomness used by the algorithm. We would like to understand how we can construct randomized algorithms which while still using the power of randomness can ensure that when run multiple time on the same input, with high probability result in the same output on each of the executions. We first show a pseudo-deterministic NC algorithm for finding matchings in bipartite graphs. As a corollary, we also show a pseudo-deterministic NC algorithm for constructing DFS trees in graphs. We then show a reproducible algorithm for problems in search-RL. That is, we show an algorithm for problems in search-RL such that the output depends only on 𝑂(log 𝑛) many random bits used by the algorithm. We also show a pseudo-deterministic log-space low time algorithm for finding paths in undirected graphs. The algorithm is much faster than deterministic logspace algorithms for the problem. Next, we investigate pseudo-determinism in the context of streaming algorithms. We show both lower and upper bounds for some classic streaming problems. Most notably, we show that the problem of approximate counting in a stream (for which the well known algorithm of Morris gives a 𝑂(log log 𝑛) space algorithm), has no pseudo-deterministic algorithms using space 𝑜(log 𝑛). Finally, we examine an extension of pseudo-determinism to the context of interactive proofs. Ph.D. 2023-07-31T19:22:49Z 2023-07-31T19:22:49Z 2023-06 2023-07-13T14:21:14.947Z Thesis https://hdl.handle.net/1721.1/151209 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Grossman, Ofer Pseudo-determinism |
| title | Pseudo-determinism |
| title_full | Pseudo-determinism |
| title_fullStr | Pseudo-determinism |
| title_full_unstemmed | Pseudo-determinism |
| title_short | Pseudo-determinism |
| title_sort | pseudo determinism |
| url | https://hdl.handle.net/1721.1/151209 |
| work_keys_str_mv | AT grossmanofer pseudodeterminism |