Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [fourier-analysis]

The tag has no usage guidance.

75 questions
Filter by
Sorted by
Tagged with
67 views

### Distance between Fourier distributions of independent random Boolean functions

For a boolean function $f: \{-1,+1\}^n \to \{-1,+1\}$, the squared Fourier coefficients $\{\hat{f}(S)^2\}_{S \subseteq \{0,1\}^n}$ form a probability distribution. I want to know what the total ...
52 views

### "Inverting" the fourier spectrum representation of a boolean function to recover a circuit representaiton

Given a boolean circuit, or an equivalent boolean expression, we can compute its fourier spectrum to yield a real-valued (multilinear) polynomial representation. What about the other way around? ...
45 views

### Is it possible to estimate the positive outcomes of a boolean function using an optimized version of Goldreich-Levin?

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 ...
• 65
1 vote
46 views

### what are some Lower bound for finding large fourier coefficients of boolean function (above a threshold)?

Is there some known lower bounds for estimating large fourier coefficients of boolean functions? And were there any comparison of tightness with the upper bound of Goldreich Levin algorithm?
• 65
46 views

### Does Goldreich-Levin algorithm for finding large Fourier coefficients have time complexity upper bound = sample complexity upper bound?

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 ...
• 65
1 vote
52 views

### Is there an efficient Goldreich-Levin algorithm that generalizes to agnostic PAC setting?

Goldreich Levin algorithm is an algorithm that based on some assumption (boundness on Fourier coefficients) outputs the indices for most significant Fourier coefficients of a boolean function, however ...
• 65
1 vote
47 views

### Compute Fourier coefficients from Single Fourier coefficient and initial vector?

I have some vector $\vec v\in\mathbb{Z}_q^n$, and would like to obtain $n$ vectors $\vec f_0,\dots, \vec f_{n-1}$ where $\vec f_i = (\mathcal{F}(\vec v)_i,0,\dots,0)$, i.e. each vector is a single ...
179 views

### What is the time complexity of fermionic Fourier transform?

Suppose $N = 2^L$ and we are interested in performing the following transformation a $\mapsto$ a_hat on arrays of $N$ complex ...
• 141
61 views

• 31
244 views

### Is there a simple argument for this Hemi-Icosahedron Boolean function?

This is problem 1(e) from Homework 1 of the course about Analysis of Boolean functions at CMU in 2012 as well as problem 1.1(n) on p.34 of Ryan O'Donnell's Analysis of Boolean Functions. Compute the ...
• 523
1 vote
35 views

### Are there uses for a Fourier transform of length $n^m$ with elements of maximum size $n$?

In essence, I'm trying to get a better feel for when there is a use for FFT with small coefficients, compared to the length, assuming that we get a better runtime. I've been toying with an idea for a ...
• 2,100
133 views

### What would faster Fourier Transform(FFT?) and/or multiplication algorithms imply?

There are many problems which have implications on P vs. NP and other complexity classes. Supposing that we're interested in Fourier transforms and/or multiplication algorithms, do faster Fourier ...
• 2,100
147 views

### On FFT and trigonometric matrix eigenvalues

Let $N=2^n$ for a natural number $n$ and $B$ be the $N\times N$ square matrix of $0$'s and $1$'s  B=\begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \\ 1 & 0 & 1 & \ldots ...
• 71
121 views

### Question about discarding the second register in the standard approach of hidden subgroup algorithm

My questions: What does discarding the second register mean for the standard approach of hidden subgroup algorithm? Why does discarding let the first register end up in a mixed state? My ...
• 651
144 views

### Dimension of the Fourier transform for $S_5$ [closed]

My question: What is the dimension of the Fourier transform for $S_5$? My effort: The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
• 651
152 views

### Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
330 views

### Sign patterns for Fourier coefficients of Boolean functions

Given a sequence of real numbers $(a_i)$, the sign-pattern sequence $(s_i)$ is defined by $s_i = +$ if $a_i \geq 0$ and $s_i = -$ otherwise. For a boolean function $f: \{0,1\}^n \to \{0,1\}$, ...
• 7,000
357 views

### $\ell_1$ norm of Fourier coefficients vector for the hypercube

Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$. Given a ...
• 225
107 views

Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\... • 2,803 5 votes 0 answers 165 views ### Fourier Analysis on checking whether there exists a vector in hypercube orthogonal to a set of vectors? I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem. My problem is: Given vectors$h_1,\cdots,h_k\in\{+1,-1\}^n$where$k < n$,... 11 votes 0 answers 174 views ### Variance of bounded functions with rapidly decaying Fourier coefficients I have the following conjecture about bounded functions on the hypercube. Any help resolving it (proof, counterexample, some ideas) is much appreciated. Conjecture. Let$f : \{ -1, +1 \}^n \to [-1, +...
• 2,803
Let $f:\{-1,1\}^n \rightarrow \{-1,1\}$ be any boolean function. Let $Maj_n$ represent the majority function. Let $\langle f,g \rangle = E[f(x)g(x)]$ and \$\mathcal{I}(f) = E_x[\# i, s.t. f(x)\neq f(x \...