An oblivious bit-fixing source is a distribution over $\{0,1\}^n$, where $k$ bits are uniform and independent and the rest $n-k$ are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity ... more >>>

Pseudodeterministic algorithms are probabilistic algorithms that solve search problems but do so by always providing the same (``canonical'') solution to a given instance, except with small probability.
While the complexity theoretic implications of pseudodeterministic algorithms were explored in the past, we suggest to conduct this exploration within the framework ... more >>>

The question of optimal derandomization, introduced by Doron et. al (JACM 2022), garnered significant recent attention. Works in recent years showed conditional superfast derandomization algorithms, as well as conditional impossibility results, and barriers for obtaining superfast derandomization using certain black-box techniques.

Of particular interest is the extreme high-end, which ... more >>>