<p>Let <span class="math-container">$\mathcal{X} = \{-1,1\}^n$</span> and <span class="math-container">$h: \mathcal{X} \to \{-1,1\}$</span>, h can be expanded in the basis of monomials for the uniform distribution, or also can have a distribution free expansion (Gram-Schmidt orthogonalization).</p>
<p>I have two questions:</p>
<ul>
<li>Goldreich-Levin algorithm is used to approximate large Fourier coefficients of a boolean function and is limited to the case of uniform distribution. Still, it seems it can be naturally generalized to the distribution-free setting while maintaining the polynomial time complexity. If true, how does the sample complexity change in the general distribution-free setting? I did the math but surprisingly it remains the same, I'm wondering if I missed something.</li>
<li>Can we express the probability of getting positive outcomes: <span class="math-container">$\mathbb{P}[h(x)=1]$</span> in terms of Fourier coefficients? And is there a known relaxed version of Goldreich-Levin + Low degree algorithm for estimating <span class="math-container">$\mathbb{P}[h(x)=1]$</span>?</li>
</ul>

CC BY-SA 4.0
2023-12-26T03:11:02.383Z
Please ask only one question per post.  When you have two questions, you can ask them separately.  I recommend that you show your work.  I suggest you define precisely what you mean by 'the distribution-free setting' and what you have concluded the sample complexity is, and show your work.
D.W.
CC BY-SA 4.0
2023-12-26T06:53:57.870Z
For the second question -- look at $\hat{h}(\emptyset)$. By definition, it's $\mathbb{E}[h(x)] = 2\mathbb{P}\{h(x)=1\}-1$. (also -- didn't you already ask the first? https://cstheory.stackexchange.com/questions/53502/is-there-an-efficient-goldreich-levin-algorithm-that-generalizes-to-agnostic-pac)
Clement C.
CC BY-SA 4.0
2023-12-26T12:09:19.710Z
@D.W. I will write the results by today and edit the post, thank you for pointing out that.
rivana
CC BY-SA 4.0
2023-12-26T12:14:48.050Z
@ClementC the first question is different from the post as here I'm concerned about to how the sample complexity changes with the distribution-free setting, which I did but seems to stay the same, I find that weird, if it's general why Goldreich-Levin is only used in the case of uniform distribution.
rivana
<boolean-functions><fourier-analysis><sample-complexity>
Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?
rivana
# Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?

(Asked by: username_0 on 2023-12-26)

Let $\mathcal{X} = \{-1,1\}^n$ and $h: \mathcal{X} \to \{-1,1\}$, h can be expanded in the basis of monomials for the uniform distribution, or also can have a distribution free expansion (Gram-Schmidt orthogonalization).

I have two questions:

* Goldreich-Levin algorithm is used to approximate large Fourier coefficients of a boolean function and is limited to the case of uniform distribution. Still, it seems it can be naturally generalized to the distribution-free setting while maintaining the polynomial time complexity. If true, how does the sample complexity change in the general distribution-free setting? I did the math but surprisingly it remains the same, I'm wondering if I missed something.
* Can we express the probability of getting positive outcomes: $\mathbb{P}[h(x)=1]$ in terms of Fourier coefficients? And is there a known relaxed version of Goldreich-Levin + Low degree algorithm for estimating $\mathbb{P}[h(x)=1]$?

**Tags:** boolean-functions, fourier-analysis, sample-complexity

> **Comments:**
> **username_1**: Please ask only one question per post.  When you have two questions, you can ask them separately.  I recommend that you show your work.  I suggest you define precisely what you mean by 'the distribution-free setting' and what you have concluded the sample complexity is, and show your work.  
> **username_2**: For the second question -- look at $\hat{h}(\emptyset)$. By definition, it's $\mathbb{E}[h(x)] = 2\mathbb{P}\{h(x)=1\}-1$. (also -- didn't you already ask the first? https://cstheory.stackexchange.com/questions/53502/is-there-an-efficient-goldreich-levin-algorithm-that-generalizes-to-agnostic-pac)  
> **username_0**: @username_1 I will write the results by today and edit the post, thank you for pointing out that.  
> **username_0**: @ClementC the first question is different from the post as here I'm concerned about to how the sample complexity changes with the distribution-free setting, which I did but seems to stay the same, I find that weird, if it's general why Goldreich-Levin is only used in the case of uniform distribution.  

---

## 0 answers

