Anon 9:07 -- By this I mean that in the phrase "$S \in H^{\bot}$", you should treat the set $S \subseteq [n]$ as the vector $s \in \mathbb{F}_2^n$ which has a $1$ in the $i$th coordinate if $i \in S$ and has a $0$ in the $i$th coordinate if $i \not \in S$.
Anon 9:18 -- Start with a function $f : \{-1,1\}^n \to \{-1,1\}$. Now imagine that you take some $c \leq d$ coordinates in $[n]$, $i_1, ..., i_c$, and you "fix" values for them, say $a_{i_1}, ..., a_{i_c} \in \{-1,1\}$. So now you get a subfunction $g$ which maps the $n-c$ unfixed variables into $\{-1,1\}$. Does that make sense? It's a bit hard to explain in text. It's like you hardwire in values for some $c$ of the inputs to $f$ and you get a new function on the remaining coordinates.
Anonymous 4:24: We always identify 0 in F_2^n with -1 in R and 1 in F_2^n with 1 in R. The function chi_S : F_2^n \to R is the function that maps x \in F_2^n to
prod_{i in S} (-1)^{x_i}.
\hat{f}(S) = E_{x in F_2^n} [f(x) chi_S(x)] under this definition.
In response to another question I got from a student: In the definition of orthogonal complement (in the notation section), the inner product of x and h means inner product **in F_2^n**. I.e., it equals sum_{i=1..n} x_i h_i mod 2.
Anon. 5:46: F_2 is the 2-element field: {0,1}, the integers mod 2. Please see my comment beginning, "Anonymous 4:24..." Two vectors are "orthogonal" in this vector space if their dot product *over F_2* is 0; e.g., (1,0,0,1) is orthogonal to (1,1,1,1) but not to (0,1,1,1). In talking about the Fourier coefficients here, S is taken to be a vector in F_2 and \hat{f}(S) = E_{x in F_2^n} [(-1)^{S dot x} f(x)], where again, the dot product is over F_2.
If you are still confused, email me or catch me after class.
Anon. 6:39: Yes, subspace is the standard linear algebra notion: a subset closed under addition. Or the linear span of a set of vectors (which, since the field just F_2, just means all subset sums).
Hint for #1: I like to write Pr[f = T] as 1/2 + rho/2 for some rho in [-1,1]. For subfunctions, I like writing 1/2 + (rho+delta)/2 and 1/2 + (rho-delta)/2.
Hint for #7b: I used something like our Håstad-based dictator test attempt, only with the natural four-query version of Håstad's test.
Hi,Ryan, in defintion 2.3 of the scribed notes of locally testable, what do u mean by 2/3 and 1/3 is arbitrary and can be boosted up? What number can replace it?
19 comments:
what does this 0-1 characteristic vector mean at problem 6??
in problem 7, what does "every function g which is a restriction of f by fixing up to d coordinates" mean?
Anon 9:07 -- By this I mean that in the phrase "$S \in H^{\bot}$", you should treat the set $S \subseteq [n]$ as the vector $s \in \mathbb{F}_2^n$ which has a $1$ in the $i$th coordinate if $i \in S$ and has a $0$ in the $i$th coordinate if $i \not \in S$.
Anon 9:18 -- Start with a function $f : \{-1,1\}^n \to \{-1,1\}$. Now imagine that you take some $c \leq d$ coordinates in $[n]$, $i_1, ..., i_c$, and you "fix" values for them, say $a_{i_1}, ..., a_{i_c} \in \{-1,1\}$. So now you get a subfunction $g$ which maps the $n-c$ unfixed variables into $\{-1,1\}$. Does that make sense? It's a bit hard to explain in text. It's like you hardwire in values for some $c$ of the inputs to $f$ and you get a new function on the remaining coordinates.
Apparently the MathHTML doesn't really work in comments. Oh well. If you're still unclear, let me know.
In problem 6, is F_2^n the space {0,1}^n, how do we define the \hat{f(s)} then? Is it still the fourier basis \chi(s)?
Anonymous 4:24: We always identify 0 in F_2^n with -1 in R and 1 in F_2^n with 1 in R. The function chi_S : F_2^n \to R is the function that maps x \in F_2^n to
prod_{i in S} (-1)^{x_i}.
\hat{f}(S) = E_{x in F_2^n} [f(x) chi_S(x)] under this definition.
In response to another question I got from a student: In the definition of orthogonal complement (in the notation section), the inner product of x and h means inner product **in F_2^n**. I.e., it equals sum_{i=1..n} x_i h_i mod 2.
Hint for #1: Induction on n.
Conjecture:
fix n and a boolean function
f:{-1,1}^n -> {-1,1}.
For i = 1,2,...,n, let p_i be the probability that flipping the i'th bit will change the value of f.
Claim:
p_i <= 2 * F_i,
where
F_i =
sum_{i \in S \subseteq [n]} \hat{f}(S)^2
in words, F_i is the sum of the squares of the Fourier coefficients corresponding to sets of indices containing i.
Is this already known to be true?
In problem 4, what do you mean by replace 1 with 2? Do you mean changing |S|>1 with |S|>2 or something else? Thanks.
The factor of 2 in my conjecture can be dropped.
This is not something related to home work 1. But thought of asking it here.
Can we make use of the same BLR test to check whether a given mapping between two groups is a homomorphism or not.
Suresh,
seems to me that the BLR test strongly exploits the product structure of {-1,1}^n. How would you set up the BLR test for a noncommutative group, say?
-Leo
Sorry for the spam, folks. The updated "conjecture" is now an identity: p_i = F_i.
I'm pretty sure this is already well known...
Leo: your final statement is correct. But save it for Homework #2! (Or perhaps next class's lecture, depending...)
Anon. 7:53:
4b means: "Show that the following is false: sum_{|S| > 2} \hat{f}(S)^2 = 0 implies f is a 2-junta."
Hi, in problem 6, is F_2 {0,1} or {-1,1}? Furthermore, is orthogonality over the reals or over F_2??
I'm quite confused.
In problem 6, what does the subspace mean? Any addition is included?
Thanks
Anon. 5:46: F_2 is the 2-element field: {0,1}, the integers mod 2. Please see my comment beginning, "Anonymous 4:24..." Two vectors are "orthogonal" in this vector space if their dot product *over F_2* is 0; e.g., (1,0,0,1) is orthogonal to (1,1,1,1) but not to (0,1,1,1). In talking about the Fourier coefficients here, S is taken to be a vector in F_2 and \hat{f}(S) = E_{x in F_2^n} [(-1)^{S dot x} f(x)], where again, the dot product is over F_2.
If you are still confused, email me or catch me after class.
Anon. 6:39: Yes, subspace is the standard linear algebra notion: a subset closed under addition. Or the linear span of a set of vectors (which, since the field just F_2, just means all subset sums).
Hint for #1: I like to write Pr[f = T] as 1/2 + rho/2 for some rho in [-1,1]. For subfunctions, I like writing 1/2 + (rho+delta)/2 and 1/2 + (rho-delta)/2.
Hint for #7b: I used something like our Håstad-based dictator test attempt, only with the natural four-query version of Håstad's test.
Hi,Ryan, in defintion 2.3 of the scribed notes of locally testable, what do u mean by 2/3 and 1/3 is arbitrary and can be boosted up? What number can replace it?
Post a Comment