Backgrounds Yao’s XOR lemma Hardcore Error correcting codes Decoding ECC Local decoding Questions Exercises Chapter 3 Locally Testable Codes with an Application in Hardness Amplification Angsheng Li Institute of Software Chinese Academy of Sciences Advanced Algorithms U CAS 6th, March, 2017 Backgrounds Yao’s XOR lemma Hardcore Error correcting codes Decoding ECC Local decoding Questions Exercises Outline 1. Backgrounds 2. Yao’s XOR 3. Impagliazzo’s hard core 4. Error correcting codes 5. Decoding ECC 6. Local decoding and hardness amplification 7. Local algorithms in networks Backgrounds Yao’s XOR lemma Hardcore Error correcting codes Decoding ECC Local decoding Questions Exercises Algebraic fundamental theorem Theorem Let p(x) be a polynomial of degree d that is given implicitly, and a finite field F. If p 6≡ 0, then there are at most d roots of p over F. Backgrounds Yao’s XOR lemma Hardcore Error correcting codes Decoding ECC Local decoding Questions Exercises
