%PDF-1.5
%
1 0 obj
<< /S /GoTo /D (section.1) >>
endobj
4 0 obj
(Spectral Sparsifiers)
endobj
5 0 obj
<< /S /GoTo /D (subsection.1.1) >>
endobj
8 0 obj
(Sparsifiers preserve cuts)
endobj
9 0 obj
<< /S /GoTo /D (section.2) >>
endobj
12 0 obj
(Review)
endobj
13 0 obj
<< /S /GoTo /D (section.3) >>
endobj
16 0 obj
(Construction of Spectral Sparsifiers)
endobj
17 0 obj
<< /S /GoTo /D (subsection.3.1) >>
endobj
20 0 obj
(A Trick: Rescaling to Isotropic Position)
endobj
21 0 obj
<< /S /GoTo /D (subsection.3.2) >>
endobj
24 0 obj
(The Proof)
endobj
25 0 obj
<< /S /GoTo /D (section.4) >>
endobj
28 0 obj
(The Koutis-Miller-Peng Algorithm)
endobj
29 0 obj
<< /S /GoTo /D (section.5) >>
endobj
32 0 obj
(Beyond Independent Sampling)
endobj
33 0 obj
<< /S /GoTo /D (subsection.5.1) >>
endobj
36 0 obj
(Linear-size sparsifiers)
endobj
37 0 obj
<< /S /GoTo /D [38 0 R /Fit] >>
endobj
42 0 obj <<
/Length 3405
/Filter /FlateDecode
>>
stream
x˒6>_#Uka7TqMmjqUq#1Hv~%Ahx]ċ7
xA\%bx/-bxos Q0.on5 J(x!
T/hL8Ĩf ,~r
^6k2|DEU{sU//4KNL۪Aph}g w/ύ!@[:;~Lt\߬4GT?ÁXLcT.C<+F%@NC}n5Tğ/W!]LEV7W2iE5'H$7w@$MMZ?d>Y-@{Uys//⸿S\HR a"J]OکG"a
Y \ċuk7s
x@&0[v7nTMG=B76y>6:=ܰ%
,JBD=̗[>Wη;|Ưp[a_$BD*-AťV
MV9=lq]q.ũ Q{n&8J-c{U`oI-!0W**2KX"N̽+}E6n:u:e;LhS_7WSYUtnr̾jUh/K ,EԴi^xTgͱhbD5IZ79
FHb%(^gq @ku M#Ω^ZC2Iy!DK
2S!\Ǿ]^pR'-T/^:3D
&!\D=9,t۱@CX `Ȟz"!z:z|;!JxLt/EBUH1yABDYQŽWCKj1 彋zhqjhio"}D|.?:V#@rAic#L{
.rF_/1|wf$"?$85'R$M2UIJ+LqD|PM_IWga3
gbY:=V,DB}¶'11
Dj8BۃO9~a0.r8p$A,$":FF]
P[Zojym![>=:VA/EHmqp;Lx~:2E@0
D+Xt1Q$K%c{= qPP$u]kS|ѡ 2)m`M.`>>5\
P!iaw)`PSGܜ3}L?pA4Ѡ{3$^*uK.9x%O$3Y1='1? wOSN }vATQ/.[sM@}
l Pbmz+UK+a*We 44nq v-[*iQ;B\]G4;%.ce(F%䪢Wpi$~V6rGIHJ1}5 :Av_ǷɐeAYIP+J}ɋeD/gV{\Nz!i =+y(|{ox`苉(oVٞL:xaLJSRut]z@d(\/w{Bۥ(mVkFrMe瞯)ƅTLFkQTۙ6
CTPS
$XUIzzJ4g6
0Zop 1Ύ7e*r5@|e7<+izS 6]8r/莰Qv\#((-q?ͶudJdnf}lzmL.vFi(5
Ԍ]
6f\46Ye"^1h/Fx ʚ!]6{KOBVn1VcS ^y;V6YYa6lRn1EbQ$M$
}},#/PY<fr3~$|o`L`&(-,Y#6,e>j Ζ;uzA%5iƻ
`6[CFPͧ0tRtQ%i*CΛMkN>iqeȓi+`v]bQDkj{`_t{~?M'>u{]ߏF8YP_g@ʼ/$֢}uU =%w`M<|buU-
>Ê sY]O|&d"LG<
1U#p@(NZ}W9oTmզE.9ቸ#`ZOlad|_gʤΝOMs|~ *pE\
cJ'ѓ ~ ޯ̩I6 !ǰJ=M^ WXwo(W҂p!
@+"
~YMiQl7Zcr_*{MU= e0dp}77tə5 2ߎfZuW*}8Ȗ!KJIw.Cŷ!C݄Նǧp7jH8 4`1I㱜0H.;a{=2zyٴbΓcqtfx7x7QHDbU?Z&6).^+ }Ny;^(|.ܱK7]rch;][I&WhB]eSÌw{gݥn}aIG֮Cigל7|p?x=sïXöbf>!0pE!nGeʪūۛ .*
endstream
endobj
38 0 obj <<
/Type /Page
/Contents 42 0 R
/Resources 41 0 R
/MediaBox [0 0 612 792]
/Parent 60 0 R
/Annots [ 39 0 R 40 0 R ]
>> endobj
39 0 obj <<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/I/C[1 0 0]
/Rect [269.646 204.378 277.093 217.28]
/A << /S /GoTo /D (equation.1.1) >>
>> endobj
40 0 obj <<
/Type /Annot
/Subtype /Link
/Border[0 0 0]/H/I/C[1 0 0]
/Rect [356.529 112.057 363.976 123.747]
/A << /S /GoTo /D (theorem.1.1) >>
>> endobj
43 0 obj <<
/D [38 0 R /XYZ -11.8 821.8 null]
>> endobj
44 0 obj <<
/D [38 0 R /XYZ 61.2 748.8 null]
>> endobj
2 0 obj <<
/D [38 0 R /XYZ 61.2 560.111 null]
>> endobj
57 0 obj <<
/D [38 0 R /XYZ 228.213 419.266 null]
>> endobj
58 0 obj <<
/D [38 0 R /XYZ 61.2 338.994 null]
>> endobj
6 0 obj <<
/D [38 0 R /XYZ 61.2 289.329 null]
>> endobj
41 0 obj <<
/Font << /F17 45 0 R /F15 46 0 R /F18 47 0 R /F19 48 0 R /F21 49 0 R /F24 50 0 R /F27 51 0 R /F25 52 0 R /F22 53 0 R /F30 54 0 R /F28 55 0 R /F42 56 0 R /F44 59 0 R >>
/ProcSet [ /PDF /Text ]
>> endobj
74 0 obj <<
/Length 3600
/Filter /FlateDecode
>>
stream
x\Y۸~Pb1A >x٭NUR-qfXYRF%ὲOIGdv9Kf$'yٌXHg3b>BFj6c<fۿb%qdIfbzMBYʷ2QYuw
jvZrkpfMvkbEcύO-=ۦD_\MU0A0PV|ޮU|w02_qLĩhŧmQem0weY]"4&ۢ!rSeeB2MiR>аBb> }PoSŅiy,l,z*[(m؞zebSe4;$}$u\郳rd² ?ym)e{)]H)ѴWR.r`\Ƙ-X2zg'Hq&L,MgQ$