2
$\begingroup$

I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function.

I was surprised seeing that the upper bounds for time complexity and sample complexity is exactly the same, do you have an explanation for that?

Improve this question
$\endgroup$
3
  • $\begingroup$ They are not exactly the same, they differ by (at least) a multiplicative constant. $\endgroup$
    – Yuval Filmus
    Nov 15 at 21:41
  • 1
    $\begingroup$ Here is another problem illustrating this phenomenon: estimating the sum of an array. $\endgroup$
    – Yuval Filmus
    Nov 15 at 21:42
  • $\begingroup$ Thank you for your answer @YuvalFilmus, I'm wondering if this also generalizes to Goldreich-Levin on the torus $\mathbb{F}_p$ (categorical instead of boolean domain)? $\endgroup$
    – rivana
    Nov 15 at 22:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.