Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with circuit lowerbounds:
TR02-008 | 11th January 2002
Valentine Kabanets

Derandomization: A Brief Overview

This survey focuses on the recent (after 1998) developments in
the area of derandomization, with the emphasis on the derandomization of
time-bounded randomized complexity classes.

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