Vi studerar Booleska funktioner med glesare Fourier spektrum eller liten spektral norm, och visar deras tillämpningar till Log-rank Conjecture för XOR funktioner f (x  på y) en ganska stor klass av funktioner inklusive väl studerade sådana som Jämlikhet och Hamming Distance. Placeringen av kommunikationsmatrisen M f för sådana funktioner är exakt den Fourier sparity av f. Låta d = deg 2 ( f ) vara F2-graden av f och D CC (f •  på) står för den deterministiska kommunikationen komplexitet för f (x  på y). Vi visar att Log-rank hypotesen håller för XOR-funktioner med konstant F2-grad. Detta förbättrar den (triviala) linjära bindningen av nästan en kvadratisk faktor. Vi får våra resultat genom en grad-minskning protokoll baserat på en variant av polynom rank, och faktiskt anta att kommunikationskostnaden för vårt protokoll är som mest log O(1) rank(M f ). Ovanstående gränser erhålls från olika analyser för antalet paritetsförfrågningar som krävs för att reducera f's F2-grad. Våra gränser innehar också för paritet beslut träd komplexitet f, en åtgärd som inte är mindre än kommunikationen komplexitet. Längs vägen visar vi också flera strukturella resultat om Booleska funktioner med liten Fourier sparity f 0 eller spektral norm f 1, som kan vara av oberoende intresse. För funktioner f med konstant F2-grad, visar vi att: 1) f kan skrivas som summan av kvasi-polynomiellt många indikatorfunktioner av subrymder med ±-tecken, förbättra den tidigare dubbelt exponentiellt övre bunden av Grön och Sanders; 2) att vara gles i Fourier domän är polynomiskt ekvivalent med att ha en liten paritet beslut träd komplexitet; och 3) f beror endast på polylog f 1 linjära funktioner av inmatningsvariabler. För funktioner f med liten spektral norm, visar vi att: 1) det finns en affin subrymd av co-dimension O( f 1) där f (x) är en konstant, och 2) det finns en paritet beslut träd djup O( f 1 log f 0) för computing f.
I ett nyligen utfört arbete med Tsang et al REF fastställdes liknande gränser som Theorem 1.1 för det särskilda fallet med funktionerna i blanketten f (x, y) = F (x  på y).
Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture
{'venue': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'journal': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}