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?

  • $\begingroup$ They are not exactly the same, they differ by (at least) a multiplicative constant. $\endgroup$ Nov 15, 2023 at 21:41
  • 1
    $\begingroup$ Here is another problem illustrating this phenomenon: estimating the sum of an array. $\endgroup$ Nov 15, 2023 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, 2023 at 22:44


Your Answer

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