Questions tagged [fourier-analysis]
The fourier-analysis tag has no usage guidance.
77 questions
3
votes
1
answer
108
views
Classical Fourier analysis for the nonabelian hidden subgroup problem
I am hoping to disentangle some subtle distinctions between solving the hidden subgroup problem on a quantum computer and performing classical Fourier analysis on functions on groups valued in fields.
...
- 131
-1
votes
1
answer
209
views
How close is a Boolean function from being a linear boolean function?
I want to prove that for every boolean function $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ the (normalized) Hamming distance from a certain linear boolean function (i.e. a boolean function $f:\mathbb{...
- 23
2
votes
0
answers
77
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 ...
- 41
4
votes
0
answers
56
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? ...
0
votes
0
answers
57
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
0
answers
54
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
2
votes
0
answers
57
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
0
answers
70
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
0
answers
50
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 ...
- 978
4
votes
1
answer
237
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
2
votes
0
answers
67
views
Learning boolean functions with input-ouput examples and side-information
The Kushilevitz-Mansour, "low-degree", and Goldreich-Levin algorithms aim to learn a function $f: \{0,1\}^n \rightarrow \{0,1\}$ from a sufficiently large set of input-output examples $(x_i, ...
1
vote
0
answers
41
views
Is there an efficient way to compute the (top entries of) the parity spectrum of a function on the Boolean cube?
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,\...
- 247
3
votes
0
answers
88
views
Harmonic analysis of sequences of Boolean functions (i.e. of words in $(\{0,1\}^n)^*$)
Is there any research on harmonic analysis of sequences of Boolean functions, which represent the application of a Boolean function on a word in $(\{0,1\}^n)^*$?
I'm looking for any reference on this, ...
- 5,636
5
votes
1
answer
488
views
A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?
As in the title.
I'm not sure where to start here. My guess is that in expectation at least a constant fraction are non zero, and as a result there would exist some "large" coefs. and some "small" ...
- 307
6
votes
1
answer
460
views
Is the basis of parity functions the only orthonormal basis for Boolean functions?
Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can ...
- 63
5
votes
2
answers
403
views
Level $k$ bounds in Analysis of Boolean functions
In Ryan O'Donnell's book Analysis of Boolean functions, following Corollary 9.25 the following appears:
If $f\colon \{-1,1\}^n \to \{0,1\}$, and we have $\mathbb{E}[f] = \alpha$, then for any integer ...
- 245
5
votes
0
answers
117
views
Majority function stability under deletion and addition of entries
It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $...
- 203
2
votes
0
answers
155
views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
- 21
4
votes
1
answer
173
views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
- 183
8
votes
2
answers
373
views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
- 183
1
vote
0
answers
68
views
relations between the degrees of a boolean function and its absolute function
Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
- 11
1
vote
0
answers
93
views
Agnostic query learning of decision trees
Gopalan, Kalai, Klivans gave an algorithm
https://dl.acm.org/citation.cfm?id=1374376.1374451
for agnostically learning decision trees $h:\{0,1\}^n\to\{0,1\}$ under the uniform distribution given ...
- 10.6k
4
votes
1
answer
319
views
Which (almost) balanced Boolean function has smallest "total" influence
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
- 41
3
votes
1
answer
258
views
Lower bound on the support size of an $\epsilon$-biased distribution
Let $D$ be an $\epsilon$-biased distribution we want to show that
$$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$
I know that there are some proofs for this but I ...
- 83
6
votes
1
answer
134
views
Average-case analogue of Small-bias Spaces
Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias
$$| \mathbb{E}_{x \in S} [ (-...
- 393
9
votes
1
answer
252
views
Has there been any progress in tightening the exponent in the result that polylog independence fools $AC_0$?
Braverman showed that distributions which are $(log \frac{m}{\epsilon})^{O(d^2)}$-wise independent $\epsilon$-fool depth $d$ $AC^0$ circuits of size $m$ by "gluing together" the Smolensky ...
- 1,582
1
vote
0
answers
76
views
Relative Two-Function Hypercontractive Inequality $\langle T_{\rho\sigma} f,g \rangle \le \langle T_{\sigma} f,g \rangle^q$
The hypercontractive theorem (or Bonami Beckner inequality) says (Ryan O'Donnell):
This of course also directly gives the 'intermediate' inequality $\|T_{\rho\sigma}f\|_q \le \|T_\sigma f\|_{1+(q-1)\...
- 958
2
votes
0
answers
109
views
$p$-biased two-function hypercontractivity
The Hypercontractivity theorem (or Bonami Beckner inequality) is a very useful tool. Unfortunately, it isn't easy to carry over to other spaces than the uniform boolean cube.
In Ryan O'Donnel's ...
- 958
2
votes
1
answer
243
views
Fourier decomposition in terms of another basis
Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S}...
- 251
4
votes
0
answers
213
views
Relationship between sparsity and rank of a boolean function
I have the following question when I was going through the proof of the following theorem.
Theorem. For XOR function $f \circ XOR$, $rank(M_{f \circ XOR}) = ||\hat f ||_0$ where $M_{f \circ XOR}$ is ...
- 345
3
votes
1
answer
235
views
Basic property of boolean functions with restrictions
For $f:\{\pm1\}^n\to\mathbb{R}$, $I\subset\{1,\dots,n\}$ and $x\in\{\pm1\}^{\{1,\dots,n\}\setminus I}$ we define $f_I[x]:\{\pm1\}^I\to\mathbb{R}$ by $f_I[x](y)=f(x,y)$. (We denote by ($x,y$) the ...
- 179
7
votes
0
answers
157
views
Are there generalizations for Chow's theorem?
The Chow's theorem as it stands holds only for a single linear threshold gate. That these gates are uniquely determined by their first $n+1$ Fourier coefficients.
Are there other circuits for which ...
- 1,453
10
votes
1
answer
258
views
Is this "subgroup packing" polytope integral?
Let $\Gamma$ be a finite abelian group, and let $P$ be the polytope in $\mathbb{R}^\Gamma$ defined to be the points $x$ satisfying the following inequalities:
$$\begin{array}{cl}
\sum_{g\in G} x_g \...
- 1,439
14
votes
0
answers
375
views
Fourier spectrum of the parity of two monotone Boolean functions
This is a question that I've been pondering, on and off, for a while, and unsuccessfully. I'd be very interested in any insight regarding this conjecture. (Or rather, these conjectures.)
Recall that, ...
- 4,491
4
votes
0
answers
164
views
About counting the "total size" of non-zero Fourier coefficients of a Boolean function
Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity,
$\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $
i.e the sum of the sizes of the subsets of $[n]$ ...
- 1,453
-1
votes
1
answer
305
views
Sparsity of a Boolean function and its Fourier depth [closed]
For a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ one can ask for its $l_0$ norm in the indicator basis i.e the number of vertices on which the function is non-zero. Does this sparsity parameter ...
- 1,453
7
votes
0
answers
129
views
Learning function with a few low-order Fourier coefficients, from uniformly random samples
Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each ...
- 12.4k
8
votes
1
answer
322
views
Is a monotone boolean function monotone as a multilinear polynomial?
Let $f:\{-1,1\}^n \rightarrow \{0,1\}$ be a monotonically increasing boolean function. That is, $f(x) \leq f(y)$, if coordinate-wise $x \leq y$. Now, let $F: [-1,1]^n \rightarrow \mathbb{R}$ be $f$ ...
- 81
1
vote
0
answers
163
views
Fourier expansion of boolean functions and affine subspaces
Let $f:\mathbb{F}^n_2\rightarrow \{0,1\}$ be a function constant on an affine subspace $V$ of co-dimension $t$. Assume that that $V$ is a linear subspace, by replacing $f(x)$ with $f(x+v)$ for some $v ...
- 31
7
votes
0
answers
256
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
0
answers
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,110
2
votes
0
answers
134
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,110
2
votes
0
answers
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
0
votes
1
answer
123
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 ...
- 661
-3
votes
1
answer
152
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 ...
- 661
2
votes
0
answers
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 ...
- 29
15
votes
0
answers
333
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,030
4
votes
1
answer
367
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
4
votes
1
answer
107
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)]\...
- 2,813
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$,...
