SCIENCE@home

New cryptographic hardness for learning intersections of halfspaces over boolean cubes with membership queries

Ning Ding,Dawu Gu

Published 2021 in Information and Computation

ABSTRACT

Abstract We revisit the PAC learnability of the class of intersections of polynomially many halfspaces over boolean cubes in the membership query model. The previous works (Klivans-Sherstov 2009, Angluin-Kharitonov 1995) imply the unlearnability of this class based on cryptographic assumptions, which is established in the case that the learner cannot generate queries of positive labels. We investigate this issue, focusing on the case that the learner is given representations of input distributions (so it may generate queries of positive and negative labels). Our result is that assuming some new cryptographic primitives, the class is still unlearnable in the query model even if the learner has representations of the distributions. The result is established via a new argument. We show that if the class is learnable, we can come up with a differing-inputs obfuscator, which, however, does not exist given the cryptographic primitives. Thus the hardness result follows from the contradiction.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-70 of 70 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1