The fourier-analysis tag has no wiki summary.
0
votes
0answers
69 views
Bound for the spectral norm of a boolean function [duplicate]
As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$.
Is it possible to improve this bound..?
Can somebody provide me an example of a Boolean ...
4
votes
1answer
300 views
Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?
Let $f: \{-1,1\}^n \rightarrow \{-1,1\}$ be a Boolean function.
The Fourier expansion of $f$ is
$$f(T) = \sum_{S \subseteq [n]} \widehat{f}(S)\ \chi_S(T)$$
where $\widehat{f}(S)$ are real numbers ...
14
votes
1answer
215 views
An extension of the noise operator
In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator ...
0
votes
0answers
92 views
General questions on Cayley graphs [closed]
In Graph Theory mainly in Cayley graphs there are four general questions " according to Audery Terras" : 'Suppose A is the adjacency operator of a connected regular (undirected)
graph $X$ of degree ...
5
votes
0answers
98 views
Upperbound on the degree of a boolean function in terms of its sensitivity
A very interesting open problem in the study of complexity measures of Boolean function is the so called sensitivity vs block sensitivity conjecture. For background on sensitivity versus block ...
16
votes
2answers
447 views
Robustness of splitting a junta
We say that a Boolean function $f: \{0,1\}^n \to \{0,1\}$ is a $k$-junta if $f$ has at most $k$ influencing variables.
Let $f: \{0,1\}^n \to \{0,1\}$ be a $2k$-junta. Denote the variables of $f$ by ...
16
votes
2answers
277 views
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
29
votes
11answers
735 views
Applications of representation theory of the symmetric group
Inspired by this question and in particular the final paragraph of Or's answer, I have the following question:
Do you know of any applications of the representation theory of the symmetric group ...
38
votes
2answers
2k views
Why does Fourier analysis of Boolean functions “work”?
Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including ...
7
votes
0answers
189 views
Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?
Result 1: Linial-Mansour-Nisan theorem says that the fourier weight of the functions computed by the $\mathsf{AC}^0$ circuits is concentrated on the subsets of small size with high probability.
...
12
votes
1answer
374 views
The entropy of a convolution over the hypercube
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
5
votes
0answers
109 views
Truncated convolution algorithm
Suppose I have $n+1$-dimensional vectors $a$ and $b$. For each $i = 0, \dots, n$, I also have integers $0 \leq j_0(i) \leq j_1(i) \leq i$. I want to compute the following variant of a convolution:
$$
...
17
votes
2answers
496 views
Linearly independent Fourier coefficients
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ ...
10
votes
0answers
166 views
Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm
What is the best known query complexity of Goldreich-Levin learning algorithm?
Lecture notes from Luca Trevisan's blog, Lemma 3, states it as $O(1/\epsilon^4 n \log n)$.
Is this the best known in ...
3
votes
1answer
189 views
Nearly Optimal Sparse Walsh-Fourier Tranform
In the recent paper: Nearly Optimal Sparse Fourier Transform[Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price], the authors show an $O(k \log n)$-time algorithm for the problem of computing the ...
4
votes
0answers
170 views
How to prove deg(f) = n iff the parity imbalance of f is non-zero?
Not sure if the notation I'm using here is standard or not. I'm going over class notes and I'm stumped over an exercise given: Show that $deg(f) = n \iff PI(f) \neq 0$.
Here $f$ is a boolean function ...
7
votes
0answers
108 views
Computing the Fourier-Walsh coefficients of an arithmetic circuit
Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the ...
10
votes
0answers
222 views
Relation beween approximate degree of a function and its Fourier coefficient.
Consider a Boolean function $f:\{0,1\}^n\to\{0,1\}$.
The degree of the function $d$ has a clear meaning in term of its Fourier coefficients, there are no weight on coefficient of degree higher than ...
25
votes
2answers
701 views
What is the complexity of distinguishing a true Fourier spectra from a fake one?
A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.
The Fourier spectra of a function $f$ is defined as ...
25
votes
1answer
1k views
Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates
Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
