# Tagged Questions

264 views

### Characterizing and counting boolean functions with all influences 1/2

Is there a characterization of boolean functions $f:\{-1,1\}^n \longrightarrow \{-1,1\}$, so that $\mathbf{Inf_i}[f]=\frac{1} {2}$, for all $1\leq i\leq n$? Is it known how many such functions there ...
341 views

### Ultrafilter-based Fourier-Walsh-like Functions

Here is a (little wild) question about Boolean functions with countably many variables and a wild analog for Fourier-Walsh functions and analysis based on them. Let $x_1,x_2,\dots,x_n,\dots$ be ...
864 views

### fourier analytic proofs

While searching through Mathoverflow, I found out a fourier analytic proof of the Isoperimetric Inequality.Also, by google search I found a fourier analytic proof of Quadratic Reciprocity theorem.I ...
302 views

### faces in the discrete cube

This arose from a question Gil Kalai asked about a problem I posed involving the Fourier transform on the discrete cube. Maybe it is more tractable. I'm afraid I'm not sure how to do this kind of ...
1k views

### Fourier transform on the discrete cube

Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$. The following is an asymptotic question. "Close to one" means "more than ...
318 views

### Kahn-Kalai-Linial for intersecting upsets

Is there any known improvement on the Kahn-Kalai-Linial inequality (on the influences of boolean functions) in the special case in which $f$ is the indicator function of an intersecting monotonic set ...
3k views

### Is there an “elegant” non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

Hi. Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway... Consider this problem. I've been trying to find a formula to expand the "regular iteration" ...
1k views

### What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
628 views

### Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

Consider functions on the discrete cube $\{-1,1\}^n$. We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of ...