Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-DETERMINISTIC REDUCTIONS:
Reports tagged with non-deterministic reductions:
TR15-051 | 5th April 2015
Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

ISSN 1433-8092 | Imprint