# Questions tagged [fourier-analysis]

The tag has no usage guidance.

74 questions
Filter by
Sorted by
Tagged with
51 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? ...
44 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
44 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
44 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
49 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
46 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 ...
• 938
172 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
60 views

• 31
238 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 ...
• 503
1 vote
33 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