<p>I'm currently working on finding better bounds for Goldreich-Levin algorithm for estimating large Fourier coefficients of a boolean function.</p>
<p>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?</p>

CC BY-SA 4.0
2023-11-15T21:41:36.083Z
They are not exactly the same, they differ by (at least) a multiplicative constant.
Yuval Filmus
CC BY-SA 4.0
2023-11-15T21:42:32.203Z
Here is another problem illustrating this phenomenon: estimating the sum of an array.
Yuval Filmus
CC BY-SA 4.0
2023-11-15T22:44:29.917Z
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)?
rivana
<time-complexity><boolean-functions><fourier-analysis><sample-complexity>
Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?
rivana
# Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?

(Asked by: username_0 on 2023-11-14)

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?

**Tags:** time-complexity, boolean-functions, fourier-analysis, sample-complexity
> **Comments:**
> **username_1**: They are not exactly the same, they differ by (at least) a multiplicative constant.  
> **username_1**: Here is another problem illustrating this phenomenon: estimating the sum of an array.  
> **username_0**: 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)?  

---

## 0 answers

