Tuesday, February 06, 2007

Homework #2

A student asked if we've already covered in lecture everything needed for Homework #2. The answer is yes.

Questions about the homework can go in the comments of this post.

2 comments:

Anonymous said...

What does "use one of the 8 posible OR3 predicate" mean in problem 6? The tester can only query one of the 8 predicate?

Ryan O'Donnell said...

Anon 9:28:

It means that the tester must act as follows:

1. Use randomness to choose 3 query positions, x_i, x_j, x_k.

2. (Possibly use additional randomness to) choose one of the 8 possible Or_3 predicates, phi.

3. Query x_i, x_j, x_k and accept iff phi(x_i,x_j,x_k).