# Questions tagged [fourier-analysis]

The tag has no usage guidance.

72 questions
Filter by
Sorted by
Tagged with
1 vote
39 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?
39 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 ...
31 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 ...
1 vote
45 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 ...
149 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 ...
58 views

234 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 ...
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 ...
132 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 ...
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 ... 0 votes 1 answer 118 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 ... -3 votes 1 answer 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 ... 2 votes 0 answers 151 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 ... 14 votes 0 answers 326 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\}, ... 4 votes 1 answer 345 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 ... 4 votes 1 answer 106 views ### Is being fooled by limited independence preserved by products? 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)]\... 5 votes 0 answers 164 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 173 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, +... 3 votes 0 answers 189 views ### An identity about the Majority function? 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 \... 0 votes 0 answers 134 views ### Determining if a function is constant or not using period finding Consider an arbitrary boolean function$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$which we write as:$$f(x_1, x_2 ... x_n) $$where each x_i is a boolean variable We note ... 0 votes 0 answers 141 views ### Computing the period of a function using a quantum computer Consider a blackbox function$$f(x): Z \rightarrow \lbrace 0,1 \rbrace $$Which inputs an integer and outputs 0 or 1 with bit complexity n. If the period P of this function satisfies$$P \in O(2^{...
consider a function $$f(x_1,x_2...x_n)$$ I am told it is possible to compute the period of the function as a vector $$<l_1,l_2...l_n>$$ where each l denotes the period of the function for ...