Publication:5368744

DOI10.4230/LIPIcs.CCC.2016.10zbMath1380.68242MaRDI QIDQ5368744

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Marco L. Carmosino

Publication date: 10 October 2017

zbMATH Keywords

learning; compression; lower bounds; circuit complexity; natural proofs

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)