Guy Kindler

The first part of this thesis strengthens the low-error PCP

characterization of NP, coming closer to the upper limit of the

conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over

$n$ variables can be tested for the property of depending ...
more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>