Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [fourier-analysis]

The tag has no usage guidance.

31 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
302 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, ...
292 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\}$, ...
157 views

107 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 ...
189 views

### An alternative proof of hypercontractivity of the Becker-Bonami operator

The Becker-Bonami operator $T_p$ on a function $f(x) : \{0,1\}^d \to \mathbb{R}$ is defined as follows. Let $\nu(x)$ be a perturbation of $x$ so that every bit remains the same with probability $p$ or ...
135 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 Fourier-...
123 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 ...
110 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 ...
162 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$,...
125 views

150 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 ...
58 views

### Is there a relation between $l_p$-norms of functions with same Fourier spectra but w.r.t different measures on the Hamming cube?

Informally, I want to ask if two functions $f$ and $g$ on the Hamming cube have the same Fourier spectra but w.r.t different measure and basis, then is $||f||_p$ related to $||g||_p$? (Where each $p$-...