All reports by Author Sergei Artemenko:

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
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

__
TR11-016
| 7th February 2011
__

Sergei Artemenko, Ronen Shaltiel#### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

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

Sergei Artemenko, Ronen Shaltiel

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>