The course blog for Carnegie Mellon Computer Science course 18-859S, offered in Spring 2007 with instructor Ryan O'Donnell.
What does "use one of the 8 posible OR3 predicate" mean in problem 6? The tester can only query one of the 8 predicate?
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).
Post a Comment