%PDF-1.5
%
4 0 obj
<< /S /GoTo /D (section.1) >>
endobj
7 0 obj
(Introduction)
endobj
8 0 obj
<< /S /GoTo /D (subsection.1.1) >>
endobj
11 0 obj
(Our Results)
endobj
12 0 obj
<< /S /GoTo /D (subsection.1.2) >>
endobj
15 0 obj
(Key Techniques)
endobj
16 0 obj
<< /S /GoTo /D (section.2) >>
endobj
19 0 obj
(Algorithm Descriptions)
endobj
20 0 obj
<< /S /GoTo /D (subsection.2.1) >>
endobj
23 0 obj
(Terminology and a Quick Exposition of the CLP Algorithm)
endobj
24 0 obj
<< /S /GoTo /D (subsection.2.2) >>
endobj
27 0 obj
(High-Level Description of our MPC Algorithm)
endobj
28 0 obj
<< /S /GoTo /D (subsection.2.3) >>
endobj
31 0 obj
(Pseudorandom Generators and Derandomization)
endobj
32 0 obj
<< /S /GoTo /D (subsection.2.4) >>
endobj
35 0 obj
(Bounded-Independence Hash Functions)
endobj
36 0 obj
<< /S /GoTo /D (subsection.2.5) >>
endobj
39 0 obj
(The Method of Conditional Expectations)
endobj
40 0 obj
<< /S /GoTo /D (section.3) >>
endobj
43 0 obj
(Reducing to Medium-Degree Instances)
endobj
44 0 obj
<< /S /GoTo /D (section.4) >>
endobj
47 0 obj
(Improved Coloring via Derandomization of CLP)
endobj
48 0 obj
<< /S /GoTo /D (subsection.4.1) >>
endobj
51 0 obj
(Low-Deg Coloring)
endobj
52 0 obj
<< /S /GoTo /D (subsection.4.2) >>
endobj
55 0 obj
(Initial Slack Generation)
endobj
56 0 obj
<< /S /GoTo /D (subsection.4.3) >>
endobj
59 0 obj
(Dense Coloring with Slack)
endobj
60 0 obj
<< /S /GoTo /D (subsection.4.4) >>
endobj
63 0 obj
(Dense Coloring without Slack)
endobj
64 0 obj
<< /S /GoTo /D (subsubsection.4.4.1) >>
endobj
67 0 obj
(Coloring Large Blocks of Layers i2)
endobj
68 0 obj
<< /S /GoTo /D (subsubsection.4.4.2) >>
endobj
71 0 obj
(Coloring Large Blocks of Layer 1)
endobj
72 0 obj
<< /S /GoTo /D (subsection.4.5) >>
endobj
75 0 obj
(Sparse Coloring)
endobj
76 0 obj
<< /S /GoTo /D (appendix.A) >>
endobj
79 0 obj
(Pseudocode for CLP Procedures)
endobj
80 0 obj
<< /S /GoTo /D (subsection.A.1) >>
endobj
83 0 obj
(Complete Analysis for Sec. 3 \(Proof of Lemma 14\))
endobj
84 0 obj
<< /S /GoTo /D (subsection.A.2) >>
endobj
87 0 obj
(Good and Bad Machines for Random Hash Functions)
endobj
88 0 obj
<< /S /GoTo /D (appendix.B) >>
endobj
91 0 obj
(Generating Initial Slack: Proof of Theorem 17)
endobj
92 0 obj
<< /S /GoTo /D (appendix.C) >>
endobj
95 0 obj
(Missing Proofs for the CLP Derandomization)
endobj
96 0 obj
<< /S /GoTo /D (subsection.C.1) >>
endobj
99 0 obj
(Handling Smaller and Unequal Palettes)
endobj
100 0 obj
<< /S /GoTo /D [101 0 R /Fit] >>
endobj
103 0 obj
<<
/Length 2415
/Filter /FlateDecode
>>
stream
xڭXݓ۸
߿o"_t&{mnz܃l3neG6__liz}E$_l|/B&EB%$v S-f+D/]}QmWܿYz,Kr˄2'bK)FgD0Q&QLȰ>˺)-.ba\RLX)*Gc|wDk3SX& )%D.-Wb2`W'UO47X,I2l!|25O'f&X6l*>-\RȂq觥Q*:
;Gr.\EPbl*gxLѮK|xk&xzWaG\9mxX}D~H&+8|}c-E1b|BN[y@!иUT{I,j:$@Ę;L# o Ge1"|pq.YS1%',#"nXpdG+Ǹ=,5sZAda'o[LqGy+ɳW3 wyWUHLNG ePc)[nǡ>
ѻu: nk$\+=[]qQq_:&g@r|&&?ZuEKkI0d
,=^
L&$>rkU 9`0MGAw.)9%8O({4_TPs#>:JT
UIMh]P!T§HVcp5sݠq,j癴Jt.:z7trӓwJ`Z7-
!ew^D&j\.yZ-u9hK;8v8(>zDWAb6q[ء5ppA]hu yVs%3ǣs&D!Rj8^"kEjAvyx@"BΌ V2aWRr_Ŧ}AF @ӚVCAK|zP5Ūy>BP|'*Vi55ʩ*>ԂZsdgBC7N֎I)P/}˫mcRf/E=^Hra}Pd
xh١0|HD ~K6klHG
4J{T)-&)>Fo<56J&̹d%Yait4
Zx$cдUca3\2dzF9d}>eFĕ-ԂXI1 v C\
j}KRWEsFHDg*<,mGU+lp͡u&uh%