Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QUANTIFIED DERANDOMIZATION:
Reports tagged with Quantified derandomization:
TR17-187 | 3rd December 2017
Roei Tell

#### A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization

The quantified derandomization problem of a circuit class $\mathcal{C}$ with a function $B:\mathbb{N}\rightarrow\mathbb{N}$ is the following: Given an input circuit $C\in\mathcal{C}$ over $n$ bits, deterministically distinguish between the case that $C$ accepts all but $B(n)$ of its inputs and the case that $C$ rejects all but $B(n)$ of its inputs. ... more >>>

TR18-115 | 11th June 2018
Valentine Kabanets, Zhenjian Lu

#### Satisfiability and Derandomization for Small Polynomial Threshold Circuits

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

TR20-065 | 2nd May 2020
Lijie Chen, Ce Jin, Ryan Williams

#### Sharp Threshold Results for Computational Complexity

We establish several sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, ... more >>>

TR21-120 | 18th August 2021
Roei Tell

#### How to Find Water in the Ocean: A Survey on Quantified Derandomization

The focus of this survey is the question of *quantified derandomization*, which was introduced by Goldreich and Wigderson (2014): Does derandomization of probabilistic algorithms become easier if we only want to derandomize algorithms that err with extremely small probability? How small does this probability need to be in order for ... more >>>

ISSN 1433-8092 | Imprint