Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

Ronen Shaltiel, Emanuele Viola

Hardness amplification is the fundamental task of

converting a $\delta$-hard function $f : {0,1}^n ->

{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,

where $f$ is $\gamma$-hard if small circuits fail to

compute $f$ on at least a $\gamma$ fraction of the

inputs. Typically, $\eps,\delta$ are small (and

$\delta=2^{-k}$ captures the case ...
more >>>

David Xiao

Learning is a central task in computer science, and there are various

formalisms for capturing the notion. One important model studied in

computational learning theory is the PAC model of Valiant (CACM 1984).

On the other hand, in cryptography the notion of ``learning nothing''

is often modelled by the simulation ...
more >>>

Roei Tell

We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about $S$ is estimates of the density of $S$ in adaptively chosen subsets of ... more >>>

Emanuele Viola

Research in the 80's and 90's showed how to construct a pseudorandom

generator from a function that is hard to compute on more than $99\%$

of the inputs. A more recent line of works showed however that if

the generator has small error, then the proof of correctness cannot

be ...
more >>>