<p>As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$. 
Is it possible to improve this bound..?</p>

<p>Can somebody provide me an example of a Boolean function whose spectral norm is more than the degree of the Fourier expansion of $f$ </p>

CC BY-SA 3.0
2013-03-06T17:29:29.627Z
In the comments to http://cstheory.stackexchange.com/questions/16730, you got an explicit example of a function whose spectral norm attains the bound $2^{n/2}$, and in particular is exponentially larger than the degree. Why do you not consider it to be an answer to your question, and why did you duplicate the question?
Emil Jeřábek
CC BY-SA 3.0
2013-03-06T18:39:05.333Z
I am looking for some simpler example
Kumar
CC BY-SA 3.0
2013-03-12T23:21:20.217Z
I think as Emil said Emanuele's simple counterexample in his comment answers your question. Closing this one as a duplicate.
Kaveh
<co.combinatorics><boolean-functions><fourier-analysis>
Bound for the spectral norm of a boolean function
Kumar
# Bound for the spectral norm of a boolean function

(Asked by: username_0 on 2013-03-06)

As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$.
Is it possible to improve this bound..?

Can somebody provide me an example of a Boolean function whose spectral norm is more than the degree of the Fourier expansion of $f$

**Tags:** co.combinatorics, boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: In the comments to http://cstheory.stackexchange.com/questions/16730, you got an explicit example of a function whose spectral norm attains the bound $2^{n/2}$, and in particular is exponentially larger than the degree. Why do you not consider it to be an answer to your question, and why did you duplicate the question?  
> **username_0**: I am looking for some simpler example  
> **username_2**: I think as Emil said Emanuele's simple counterexample in his comment answers your question. Closing this one as a duplicate.  

---

## 0 answers

