Average-case complexity: Difference between revisions

Revision as of 17:30, 16 May 2018

Revision as of 14:49, 20 August 2018

Line 22:

<math>

\Pr_{x \in_R D_n} \left[t_A(x) \geq t \right] \leq \frac{p(n)}{t^\epsilon}

</math>

Line 28:

<math>

E_{x \in_R D_n} \left[ \frac{t_{A}(x)^{\epsilon}}{n} \right] \leq C

</math>