1
$\begingroup$

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{avg}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the average case hardness, if $\forall$ circuit $C_n$ of size $H_{avg}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+\epsilon$, $\epsilon >0$.

Similarly, for a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$, $H_{wrs}(f)$ is a function from $\mathbb{N}\longrightarrow \mathbb{N}$, termed as the worst case hardness, if $\forall$ circuit $C_n$ of size $H_{wrs}(f)(n)$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1$.

This I know from the definition of average and worst case hardness. My question is what is the motivation behind these definitions. Can anyone help?

$\endgroup$
2
$\begingroup$

In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$.

In the worst case, you want the circuit to succeed in computing the function for all inputs, so you want to say that $f$ is at least $H(n)$ worst case hard if any circuit of size $\le H(n)$ disagrees with $f$ on at least one input in $\{0,1\}^n$.

$\endgroup$
  • $\begingroup$ Thanks, this clears the doubt I had. $\endgroup$ – roydiptajit Nov 21 '20 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.