Vi ger de första representation-oberoende hårdhetsresultat för PAC lärande skärningspunkter av halvrymder, en central koncept klass i beräkningslära teori. Våra hårdhetsresultat är härledda från två publika kryptosystem på grund av Regev, som är baserade på den värsta-fall hårdheten av välstuderade lattice problem. Specifikt visar vi att en polynom-tidsalgoritm för PAC inlärning skärningspunkter av n halvrymder (för en konstant > 0) i n dimensioner skulle ge en polynom-tid lösning tõ O(n 1.5 )-uSVP (unique kortaste vektor problem). Vi visar också att PAC lärande skärningspunkter av n låg vikt halvrymder skulle ge en polynom-tid kvantlösning tõ O(n 1.5 )-SVP och Õ(n 1.5 )-SIVP (kortaste vektor problem respektive kortaste oberoende vektor problem, respektive). Genom att göra starkare antaganden om hårdheten hos uSVP, SVP och SIVP visar vi att det inte finns någon polynom-tidsalgoritm för att lära skärningspunkter av log c n halvrymder i n dimensioner, för c > 0 tillräckligt stora. Vårt tillvägagångssätt ger också de första representation-oberoende hårdhetsresultat för att lära polynom storlek djup-2 neurala nätverk och polynom storlek djup-3 aritmetiska kretsar.
Som nämnts tidigare, det viktigaste verktyget vi förlitar oss på för att härleda hårdheten resultatet är representationen oberoende hårdhet resultat för lärande skärningspunkter av halvrymder ges i REF.
Cryptographic Hardness for Learning Intersections of Halfspaces
{'venue': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'journal': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'mag_field_of_study': ['Mathematics', 'Computer Science']}