Questions tagged [fourier-analysis]
The fourier-analysis tag has no usage guidance.
72
questions
1
vote
0
answers
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?
- 53
2
votes
0
answers
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 ...
- 53
0
votes
0
answers
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 ...
- 53
1
vote
0
answers
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 ...
- 918
4
votes
1
answer
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 ...
- 141
2
votes
0
answers
58
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
39
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
4
votes
0
answers
86
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,531
5
votes
1
answer
378
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" ...
- 187
6
votes
1
answer
420
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
4
votes
1
answer
270
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 ...
- 235
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
150
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
162
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 ...
- 173
7
votes
2
answers
356
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 ...
- 173
1
vote
0
answers
61
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
91
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.3k
4
votes
1
answer
280
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
249
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} [ (-...
- 383
9
votes
1
answer
244
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,572
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
81
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
235
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
206
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
217
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 ...
- 117
7
votes
0
answers
153
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,443
10
votes
1
answer
257
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,429
14
votes
0
answers
364
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,451
4
votes
0
answers
163
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,443
-1
votes
1
answer
279
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,443
7
votes
0
answers
122
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 ...
- 11.7k
8
votes
1
answer
306
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
145
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
6
votes
0
answers
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 ...
- 503
1
vote
0
answers
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
2
votes
0
answers
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 ...
- 2,100
2
votes
0
answers
145
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
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 ...
- 653
-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 ...
- 653
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 ...
- 29
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\}$, ...
- 6,970
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 ...
- 225
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)]\...
- 2,803
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, +...
- 2,803
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 \...
- 666
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 ...
- 369
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^{...
- 369
1
vote
0
answers
99
views
Period of a Multivariable Function using Quantum Computing
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 ...
- 369