All Questions
Tagged with fourier-analysis reference-request
6 questions
3
votes
0
answers
88
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,636
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
109
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
0
answers
106
views
Geometry on a space of polynomial functions
I am considering some geometric concepts in a space of functions.But I am not sure the concept I consider is already defined in some references.
Let $P_{1},...,P_{N}:\mathbb{F}_{2}^{n}\rightarrow \...
- 171
11
votes
1
answer
409
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 ...
14
votes
1
answer
721
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 ...
- 1,478