A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [fourier-analysis]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
176 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 ...
105 views

49 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 ...
192 views

163 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$,...
160 views

124 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 ...
126 views

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 $T_{\... 1answer 332 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 ... 2answers 764 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$...
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 ?