Tight Hardness of the Non-Commutative Grothendieck Problem.

Jop Briët Oded Regev Rishi Saket

Published in: Theory Comput. (2017)

Keyphrases

worst case
lower bound
np complete
np hard
upper bound
learning theory
computational complexity
generalization error bounds
neural network
special case
multiscale
information theoretic
phase transition
search engine
databases
database systems
mutual information
np hardness
random instances
database