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

ISSN 1433-8092 | Imprint