Abstract :
The following topics are dealt with: computational complexity; improved direct product theorems; branching programs; Max-2Lin hardness; Max-3Lin hardness; query complexity; nonnegatively weighted #CSP; symmetrix LDPC codes; locally testable codes; linear-algebraic list decoding; noise interpolation; Parris-Harrington tautologies; nonuniform ACC circuit lower bounds; affine extractors; affine dispensers; near-optimal inequality violations; explicit bell inequality violations; approximation algorithms; Arthur Merlin games; symmetric Boolean functions; property testing; communication complexity; derandomizing polynomial identity testing; tensor rank; sum of square roots; and finite Abelian groups.
Keywords :
Boolean functions; approximation theory; communication complexity; constraint theory; game theory; group theory; interpolation; linear codes; parity check codes; query processing; tensors; Arthur Merlin games; Max-2Lin hardness; Max-3Lin hardness; Parris-Harrington tautologies; affine dispensers; affine extractors; approximation algorithms; branching programs; communication complexity; computational complexity; derandomizing polynomial identity testing; explicit bell inequality violations; finite Abelian groups; improved direct product theorems; linear-algebraic list decoding; locally testable codes; near-optimal inequality violations; noise interpolation; nonnegatively weighted #CSP; nonuniform ACC circuit lower bounds; property testing; query complexity; sum of square roots; symmetric Boolean functions; symmetrix LDPC codes; tensor rank;
Conference_Titel :
Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on
Conference_Location :
San Jose, CA
Print_ISBN :
978-1-4577-0179-5
DOI :
10.1109/CCC.2011.42
