<p>Suppose I have the Boolaen cube <span class="math-container">$B=\{-1, 1\}^n$</span>, and let <span class="math-container">$F$</span> be the <span class="math-container">$2^n$</span> dimensional space of real-valued functions on it. Then the parity functions form a basis for <span class="math-container">$F$</span>:</p>
<p><span class="math-container">$$b_S(x)=\prod_{i\in S}x_i,\quad S\subseteq \{1,...,n\}$$</span></p>
<p>For an arbitrary function <span class="math-container">$f\in F$</span>, I would like to compute the <em>top</em> (in absolute value) coordinates of <span class="math-container">$f$</span> with respect to the parity basis. I would like to do this for values of <span class="math-container">$n$</span> in the hundreds or thousands, which rules out something like the <a href="https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform" rel="nofollow noreferrer">Hadamard transform</a> which is still super-exponential in <span class="math-container">$n$</span>. Is what I'm trying to do even possible?</p>
<p>I would basically like to do something like &quot;compression&quot;, like grabbing just the top few terms in a signal's Fourier series. Maybe getting the top coordinates by absolute value isn't even the &quot;right&quot; way to do this?</p>

CC BY-SA 4.0
2022-08-18T20:25:00.447Z
The first thing I'd try is to find the complexity of the subproblem where $f$ is one of the $b_S$, so that computing the top coordinates amounts to finding $S$.
xavierm02
CC BY-SA 4.0
2022-08-19T12:40:43.470Z
what is your exact definition of "top"? The top $k$ coefficients in terms of absolute value? The smallest number $k$ of coefficients whose sum of squares is above some threshold? what is the goal of this "compression"?
kodlu
CC BY-SA 4.0
2022-08-20T05:51:09.057Z
You seem to be asking for the Kushilevitz-Mansour algorithm (see, e.g., Theorem 38 in [these lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lectures_full.pdf).
Clement C.
CC BY-SA 4.0
2022-08-20T11:33:44.517Z
@ClementC. Yes, I've been reading the book by Ryan O'Donnell in the meantime and came across that, I haven't gotten into it yet but it struck me as relevant immediately
Jack M
<fourier-analysis>
Is there an efficient way to compute the (top entries of) the parity spectrum of a function on the Boolean cube?
Jack M
# Is there an efficient way to compute the (top entries of) the parity spectrum of a function on the Boolean cube?

(Asked by: username_0 on 2022-08-18)

Suppose I have the Boolaen cube $B=\{-1, 1\}^n$, and let $F$ be the $2^n$ dimensional space of real-valued functions on it. Then the parity functions form a basis for $F$:

$$b\_S(x)=\prod\_{i\in S}x\_i,\quad S\subseteq \{1,...,n\}$$

For an arbitrary function $f\in F$, I would like to compute the *top* (in absolute value) coordinates of $f$ with respect to the parity basis. I would like to do this for values of $n$ in the hundreds or thousands, which rules out something like the [Hadamard transform](https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform) which is still super-exponential in $n$. Is what I'm trying to do even possible?

I would basically like to do something like "compression", like grabbing just the top few terms in a signal's Fourier series. Maybe getting the top coordinates by absolute value isn't even the "right" way to do this?

**Tags:** fourier-analysis
> **Comments:**
> **username_1**: The first thing I'd try is to find the complexity of the subproblem where $f$ is one of the $b_S$, so that computing the top coordinates amounts to finding $S$.  
> **username_2**: what is your exact definition of "top"? The top $k$ coefficients in terms of absolute value? The smallest number $k$ of coefficients whose sum of squares is above some threshold? what is the goal of this "compression"?  
> **username_3**: You seem to be asking for the Kushilevitz-Mansour algorithm (see, e.g., Theorem 38 in [these lecture notes](http://www.cs.columbia.edu/~rocco/Teaching/S14/Scribe/lectures_full.pdf).  
> **username_0**: @ClementC. Yes, I've been reading the book by Ryan O'Donnell in the meantime and came across that, I haven't gotten into it yet but it struck me as relevant immediately  

---

## 0 answers

