Linjära skisser är kraftfulla algoritmiska verktyg som omvandlar en ndimensionell ingång till en koncis lägre-dimensionell representation via en linjär omvandling. Sådana skisser har sett ett brett spektrum av tillämpningar inklusive normuppskattning över dataströmmar, komprimerad avkänning och distribuerad databehandling. I nästan varje realistisk miljö står dock en linjär skiss inför möjligheten att dess indata korreleras med tidigare utvärderingar av skissen. Kända tekniker garanterar inte längre att produktionen är korrekt i närvaro av sådana korrelationer. Vi frågar därför: Är linjära skisser i sig icke-robust till adaptivt valda ingångar? Vi ger ett starkt positivt svar på denna fråga. Specifikt visar vi att ingen linjär skiss motsvarar den euklideiska normen för dess input inom en godtycklig multiplikativ approximationsfaktor på ett polynomtal adaptivt valda ingångar. Resultatet förblir sant även om dimensionen av skissen är d = n − o(n) och skissen ges obegränsad beräkningstid. Vårt resultat är baserat på en algoritm med körtid polynom i d som adaptivt finner en fördelning över ingångar där skissen är felaktig med konstant sannolikhet. Vårt resultat innebär flera korollärer för relaterade problem, inklusive p-normuppskattning och komprimerad avkänning. Särskilt löser vi ett öppet problem i komprimerad avkänning beträffande genomförbarheten av 2 / 2 - återvinningsgarantier i närvaro av beräkningsbundna motståndare.
Vårt arbete var också inspirerat av det senaste arbetet av Hardt och Woodruff REF, som visade att ingen lågdimensionell linjär skiss kan ge giltiga svar på även ett polynom antal adaptivt utvalda frågor.
How robust are linear sketches to adaptive inputs?
{'venue': "STOC '13", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}