Hardness of boolean functions

Question

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?

Answer 1

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