Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with pseudodeterminism:
TR18-122 | 3rd July 2018
Igor Carboni Oliveira, Rahul Santhanam

Pseudo-derandomizing learning and approximation

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser
[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed
output with high probability. We explore pseudo-determinism in the settings of learning and ap-
proximation. Our goal is to simulate known randomized algorithms in these settings ... more >>>

TR21-043 | 15th March 2021
Peter Dixon, A. Pavan, N. V. Vinodchandran

Promise Problems Meet Pseudodeterminism

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

TR23-076 | 24th May 2023
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Polynomial-Time Pseudodeterministic Construction of Primes

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>

ISSN 1433-8092 | Imprint