Abstract :
The following topics are dealt with: two prover games; derandomized parallel repetition theorems; random strings; derandomizing Arthur-Merlin games; SAT; basing cryptographic primitives; average-case complexity theory; planar acyclic digraphs; stack machines; time bounded auxiliary pushdown automata; low-weight approximation; communication complexity; and locally self-correctable codes.
Keywords :
approximation theory; automata theory; communication complexity; computability; cryptography; directed graphs; game theory; SAT; average-case complexity theory; basing cryptographic primitives; communication complexity; derandomized parallel repetition theorems; derandomizing Arthur-Merlin games; locally self-correctable codes; low-weight approximation; planar acyclic digraphs; random strings; stack machines; time bounded auxiliary pushdown automata; two prover games;
Conference_Titel :
Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4244-7214-7
