Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudo-deterministic:
TR15-207 | 23rd December 2015
Ofer Grossman

Finding Primitive Roots Pseudo-Deterministically

Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous ... more >>>

TR15-208 | 26th December 2015
Shafi Goldwasser, Ofer Grossman

Perfect Bipartite Matching in Pseudo-Deterministic $RNC$

Revisions: 2

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

TR16-196 | 5th December 2016
Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Constructions in Subexponential Time

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

TR17-105 | 14th June 2017
Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

Pseudo-Deterministic Proofs

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where
the verifier is guaranteed with high probability to output the same output on different executions.
As in the case with classical interactive proofs,
the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

... more >>>

TR18-048 | 11th March 2018
Ofer Grossman, Yang P. Liu

Reproducibility and Pseudo-Determinism in Log-Space

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 ... more >>>

TR19-135 | 2nd October 2019
Michel Goemans, Shafi Goldwasser, Dhiraj Holden

Doubly-Efficient Pseudo-Deterministic Proofs

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>

TR19-177 | 6th December 2019
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff

Pseudo-deterministic Streaming

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, $\ell_2$ approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>

ISSN 1433-8092 | Imprint