Ausgabe 1/2017
Inhalt (8 Artikel)
Sparse affine-invariant linear codes are locally testable
Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Barış Aydınlıoğlu, Dieter van Melkebeek
The Value of Help Bits in Randomized and Average-Case Complexity
Salman Beigi, Omid Etesami, Amin Gohari
Information-theoretic approximations of the nonnegative rank
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Multipartite Quantum Correlation and Communication Complexities
Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang
On the Structure of Boolean Functions with Small Spectral Norm
Amir Shpilka, Avishay Tal, Ben lee Volk