The relation between list decoding and hard-core predicates has provided a clean and easy methodology to prove the hardness of certain predicates. So far this methodology has only been used to prove that the O(log logN) ...