We prove that if the hardness of inverting a size-verifiable one-way function can
be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This
claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but
was later retracted (STOC 2010).

more >>>

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>>

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>>