PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring.

Irit Dinur Venkatesan Guruswami

Published in: FOCS (2013)

Keyphrases

low degree
agnostic learning
higher order
threshold functions
np hard
uniform distribution
computational complexity
machine learning
pairwise
np complete
model selection
theoretical analysis
phase transition
learning theory
decision lists