Wednesday, January 24, 2007

Homework 1

The comments section of this post is for questions/discussion about Homework 1.

19 comments:

Anonymous said...

what does this 0-1 characteristic vector mean at problem 6??

Anonymous said...

in problem 7, what does "every function g which is a restriction of f by fixing up to d coordinates" mean?

Ryan O'Donnell said...

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.

Ryan O'Donnell said...

Apparently the MathHTML doesn't really work in comments. Oh well. If you're still unclear, let me know.

Anonymous said...

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)?

Ryan O'Donnell said...

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.

Aryeh said...

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?

Anonymous said...

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.

Aryeh said...

The factor of 2 in my conjecture can be dropped.

Anonymous said...

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.

Aryeh said...

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

Aryeh said...

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...

Ryan O'Donnell said...

Leo: your final statement is correct. But save it for Homework #2! (Or perhaps next class's lecture, depending...)

Ryan O'Donnell said...

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."

Anonymous said...

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.

Anonymous said...

In problem 6, what does the subspace mean? Any addition is included?

Thanks

Ryan O'Donnell said...

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).

Ryan O'Donnell said...

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.

Anonymous said...

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?