<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mv="http://macVmlSchemaUri" xmlns="http://www.w3.org/TR/REC-html40"> <head> <meta name=Title content=" COMPSCI 534: Computational Complexity"> <meta name=Keywords content=""> <meta http-equiv=Content-Type content="text/html; charset=unicode"> <meta name=ProgId content=Word.Document> <meta name=Generator content="Microsoft Word 14"> <meta name=Originator content="Microsoft Word 14"> <link rel=File-List href="index_files/filelist.xml"> <link rel=Edit-Time-Data href="index_files/editdata.mso"> <!--[if !mso]> <style> v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} </style> <![endif]--> <title> COMPSCI 534: Computational Complexity</title> <!--[if gte mso 9]><xml> <o:DocumentProperties> <o:Author>John Reif</o:Author> <o:Template>Normal</o:Template> <o:LastAuthor>John Reif</o:LastAuthor> <o:Revision>2</o:Revision> <o:TotalTime>8</o:TotalTime> <o:Created>2017-04-28T03:23:00Z</o:Created> <o:LastSaved>2017-04-28T03:23:00Z</o:LastSaved> <o:Pages>2</o:Pages> <o:Words>665</o:Words> <o:Characters>3793</o:Characters> <o:Company>Duke University</o:Company> <o:Lines>31</o:Lines> <o:Paragraphs>8</o:Paragraphs> <o:CharactersWithSpaces>4450</o:CharactersWithSpaces> <o:Version>14.0</o:Version> </o:DocumentProperties> <o:OfficeDocumentSettings> <o:AllowPNG/> </o:OfficeDocumentSettings> </xml><![endif]--> <link rel=themeData href="index_files/themedata.xml"> <!--[if gte mso 9]><xml> <w:WordDocument> <w:Zoom>BestFit</w:Zoom> <w:SpellingState>Clean</w:SpellingState> <w:GrammarState>Clean</w:GrammarState> <w:TrackMoves>false</w:TrackMoves> <w:TrackFormatting/> <w:ValidateAgainstSchemas/> <w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid> <w:IgnoreMixedContent>false</w:IgnoreMixedContent> <w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText> <w:DoNotPromoteQF/> <w:LidThemeOther>EN-US</w:LidThemeOther> <w:LidThemeAsian>JA</w:LidThemeAsian> <w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript> <w:Compatibility> <w:BreakWrappedTables/> <w:SnapToGridInCell/> <w:WrapTextWithPunct/> <w:UseAsianBreakRules/> <w:DontGrowAutofit/> <w:DontUseIndentAsNumberingTabStop/> <w:FELineBreak11/> <w:WW11IndentRules/> <w:DontAutofitConstrainedTables/> <w:AutofitLikeWW11/> <w:HangulWidthLikeWW11/> <w:UseNormalStyleForList/> <w:DontVertAlignCellWithSp/> <w:DontBreakConstrainedForcedTables/> <w:DontVertAlignInTxbx/> <w:Word11KerningPairs/> <w:CachedColBalance/> </w:Compatibility> <m:mathPr> <m:mathFont m:val="Cambria Math"/> <m:brkBin m:val="before"/> <m:brkBinSub m:val="&#45;-"/> <m:smallFrac m:val="off"/> <m:dispDef/> <m:lMargin m:val="0"/> <m:rMargin m:val="0"/> <m:defJc m:val="centerGroup"/> <m:wrapIndent m:val="1440"/> <m:intLim m:val="subSup"/> <m:naryLim m:val="undOvr"/> </m:mathPr></w:WordDocument> </xml><![endif]--><!--[if gte mso 9]><xml> <w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="true" DefSemiHidden="true" DefQFormat="false" DefPriority="99" LatentStyleCount="276"> <w:LsdException Locked="false" Priority="0" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Normal"/> <w:LsdException Locked="false" Priority="9" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="heading 1"/> <w:LsdException Locked="false" Priority="9" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="heading 2"/> <w:LsdException Locked="false" Priority="9" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="heading 3"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 4"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 5"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 6"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 7"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 8"/> <w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 9"/> <w:LsdException Locked="false" Priority="39" Name="toc 1"/> <w:LsdException Locked="false" Priority="39" Name="toc 2"/> <w:LsdException Locked="false" Priority="39" Name="toc 3"/> <w:LsdException Locked="false" Priority="39" Name="toc 4"/> <w:LsdException Locked="false" Priority="39" Name="toc 5"/> <w:LsdException Locked="false" Priority="39" Name="toc 6"/> <w:LsdException Locked="false" Priority="39" Name="toc 7"/> <w:LsdException Locked="false" Priority="39" Name="toc 8"/> <w:LsdException Locked="false" Priority="39" Name="toc 9"/> <w:LsdException Locked="false" Priority="35" QFormat="true" Name="caption"/> <w:LsdException Locked="false" Priority="10" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Title"/> <w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/> <w:LsdException Locked="false" Priority="11" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtitle"/> <w:LsdException Locked="false" Priority="22" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Strong"/> <w:LsdException Locked="false" Priority="20" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Emphasis"/> <w:LsdException Locked="false" Priority="59" SemiHidden="false" UnhideWhenUsed="false" Name="Table Grid"/> <w:LsdException Locked="false" UnhideWhenUsed="false" Name="Placeholder Text"/> <w:LsdException Locked="false" Priority="1" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="No Spacing"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 1"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 1"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 1"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 1"/> <w:LsdException Locked="false" UnhideWhenUsed="false" Name="Revision"/> <w:LsdException Locked="false" Priority="34" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="List Paragraph"/> <w:LsdException Locked="false" Priority="29" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Quote"/> <w:LsdException Locked="false" Priority="30" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Quote"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 1"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 1"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 1"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 1"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 1"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 2"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 2"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 2"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 2"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 2"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 2"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 2"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 2"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 2"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 3"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 3"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 3"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 3"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 3"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 3"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 3"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 3"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 3"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 4"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 4"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 4"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 4"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 4"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 4"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 4"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 4"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 4"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 5"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 5"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 5"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 5"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 5"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 5"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 5"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 5"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 5"/> <w:LsdException Locked="false" Priority="60" SemiHidden="false" UnhideWhenUsed="false" Name="Light Shading Accent 6"/> <w:LsdException Locked="false" Priority="61" SemiHidden="false" UnhideWhenUsed="false" Name="Light List Accent 6"/> <w:LsdException Locked="false" Priority="62" SemiHidden="false" UnhideWhenUsed="false" Name="Light Grid Accent 6"/> <w:LsdException Locked="false" Priority="63" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6"/> <w:LsdException Locked="false" Priority="64" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6"/> <w:LsdException Locked="false" Priority="65" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 1 Accent 6"/> <w:LsdException Locked="false" Priority="66" SemiHidden="false" UnhideWhenUsed="false" Name="Medium List 2 Accent 6"/> <w:LsdException Locked="false" Priority="67" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6"/> <w:LsdException Locked="false" Priority="68" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6"/> <w:LsdException Locked="false" Priority="69" SemiHidden="false" UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6"/> <w:LsdException Locked="false" Priority="70" SemiHidden="false" UnhideWhenUsed="false" Name="Dark List Accent 6"/> <w:LsdException Locked="false" Priority="71" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Shading Accent 6"/> <w:LsdException Locked="false" Priority="72" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful List Accent 6"/> <w:LsdException Locked="false" Priority="73" SemiHidden="false" UnhideWhenUsed="false" Name="Colorful Grid Accent 6"/> <w:LsdException Locked="false" Priority="19" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis"/> <w:LsdException Locked="false" Priority="21" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis"/> <w:LsdException Locked="false" Priority="31" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference"/> <w:LsdException Locked="false" Priority="32" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Intense Reference"/> <w:LsdException Locked="false" Priority="33" SemiHidden="false" UnhideWhenUsed="false" QFormat="true" Name="Book Title"/> <w:LsdException Locked="false" Priority="37" Name="Bibliography"/> <w:LsdException Locked="false" Priority="39" QFormat="true" Name="TOC Heading"/> </w:LatentStyles> </xml><![endif]--> <style> <!-- /* Font Definitions */ @font-face {font-family:Arial; panose-1:2 11 6 4 2 2 2 2 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-536859905 -1073711037 9 0 511 0;} @font-face {font-family:"Courier New"; panose-1:2 7 3 9 2 2 5 2 4 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-536859905 -1073711037 9 0 511 0;} @font-face {font-family:Times; panose-1:2 0 5 0 0 0 0 0 0 0; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} @font-face {font-family:Wingdings; panose-1:5 0 0 0 0 0 0 0 0 0; mso-font-charset:2; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:0 268435456 0 0 -2147483648 0;} @font-face {font-family:"-3 0000"; mso-font-charset:78; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-536870145 1791491579 18 0 131231 0;} @font-face {font-family:"-3 0000"; mso-font-charset:78; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-536870145 1791491579 18 0 131231 0;} @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-1610611985 1073750139 0 0 159 0;} @font-face {font-family:T2; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:"Times New Roman"; mso-font-charset:77; mso-generic-font-family:swiss; mso-font-format:other; mso-font-pitch:auto; mso-font-signature:3 0 0 0 1 0;} @font-face {font-family:"CMC Smallcaps 10"; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-alt:"Times New Roman"; mso-font-charset:0; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:auto; mso-font-signature:50331648 0 0 0 1 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:10.0pt; font-family:Times; mso-fareast-font-family:"Times New Roman"; mso-bidi-font-family:"Times New Roman"; color:#494949;} h2 {mso-style-priority:9; mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 2 Char"; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; mso-outline-level:2; font-size:18.0pt; mso-bidi-font-size:10.0pt; font-family:Times; mso-fareast-font-family:"Times New Roman"; color:#494949; font-weight:bold; mso-bidi-font-weight:normal;} h3 {mso-style-priority:9; mso-style-unhide:no; mso-style-qformat:yes; mso-style-link:"Heading 3 Char"; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; mso-outline-level:3; font-size:13.5pt; mso-bidi-font-size:10.0pt; font-family:Times; mso-fareast-font-family:"Times New Roman"; color:#494949; font-weight:bold; mso-bidi-font-weight:normal;} a:link, span.MsoHyperlink {mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; color:#0F0FCE; text-decoration:underline; text-underline:single;} a:visited, span.MsoHyperlinkFollowed {mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; color:#19199E; text-decoration:underline; text-underline:single;} p {mso-style-noshow:yes; mso-style-priority:99; mso-margin-top-alt:auto; margin-right:0in; mso-margin-bottom-alt:auto; margin-left:0in; mso-pagination:widow-orphan; font-size:10.0pt; font-family:Times; mso-fareast-font-family:Times; mso-bidi-font-family:"Times New Roman"; color:#494949;} span.Heading2Char {mso-style-name:"Heading 2 Char"; mso-style-priority:9; mso-style-unhide:no; mso-style-locked:yes; mso-style-parent:""; mso-style-link:"Heading 2"; mso-ansi-font-size:13.0pt; mso-bidi-font-size:13.0pt; font-family:Calibri; mso-ascii-font-family:Calibri; mso-fareast-font-family:"-3 0000"; mso-hansi-font-family:Calibri; mso-bidi-font-family:"Times New Roman"; color:#4F81BD; font-weight:bold;} span.Heading3Char {mso-style-name:"Heading 3 Char"; mso-style-priority:9; mso-style-unhide:no; mso-style-locked:yes; mso-style-parent:""; mso-style-link:"Heading 3"; font-family:Calibri; mso-ascii-font-family:Calibri; mso-fareast-font-family:"-3 0000"; mso-hansi-font-family:Calibri; mso-bidi-font-family:"Times New Roman"; color:#4F81BD; font-weight:bold;} p.Default, li.Default, div.Default {mso-style-name:Default; mso-style-unhide:no; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:none; mso-layout-grid-align:none; text-autospace:none; font-size:12.0pt; mso-bidi-font-size:10.0pt; font-family:"CMC Smallcaps 10","serif"; mso-fareast-font-family:"Times New Roman"; mso-hansi-font-family:"CMC Smallcaps 10"; mso-bidi-font-family:"Times New Roman"; color:black;} span.SpellE {mso-style-name:""; mso-spl-e:yes;} span.GramE {mso-style-name:""; mso-gram-e:yes;} @page WordSection1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.WordSection1 {page:WordSection1;} /* List Definitions */ @list l0 {mso-list-id:199510340; mso-list-type:hybrid; mso-list-template-ids:-648654040 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l0:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.75in; mso-level-number-position:left; margin-left:.75in; text-indent:-.25in; font-family:Symbol;} @list l0:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l0:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1 {mso-list-id:1090933331; mso-list-type:hybrid; mso-list-template-ids:426405920 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l1:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l1:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l1:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2 {mso-list-id:1352537632; mso-list-type:hybrid; mso-list-template-ids:99544028 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l2:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l2:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l2:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3 {mso-list-id:1577859948; mso-list-type:hybrid; mso-list-template-ids:-856021662 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l3:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l3:level2 {mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level3 {mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level4 {mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level5 {mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level6 {mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level7 {mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level8 {mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in;} @list l3:level9 {mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in;} @list l4 {mso-list-id:1627351607; mso-list-type:hybrid; mso-list-template-ids:734134638 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l4:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l4:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l4:level3 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l4:level4 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l4:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l4:level6 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l4:level7 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l4:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l4:level9 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l5 {mso-list-id:1887451440; mso-list-type:hybrid; mso-list-template-ids:1133290104 66569 197641 328713 66569 197641 328713 66569 197641 328713;} @list l5:level1 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l5:level2 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:1.0in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l5:level3 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:1.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l5:level4 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:2.0in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l5:level5 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:2.5in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l5:level6 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:3.0in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} @list l5:level7 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:3.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Symbol;} @list l5:level8 {mso-level-number-format:bullet; mso-level-text:o; mso-level-tab-stop:4.0in; mso-level-number-position:left; text-indent:-.25in; font-family:"Courier New"; mso-bidi-font-family:"Times New Roman";} @list l5:level9 {mso-level-number-format:bullet; mso-level-text:; mso-level-tab-stop:4.5in; mso-level-number-position:left; text-indent:-.25in; font-family:Wingdings;} --> </style> <!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:10.0pt; font-family:"Times New Roman";} </style> <![endif]--><!--[if gte mso 9]><xml> <o:shapedefaults v:ext="edit" spidmax="2050"/> </xml><![endif]--><!--[if gte mso 9]><xml> <o:shapelayout v:ext="edit"> <o:idmap v:ext="edit" data="1"/> </o:shapelayout></xml><![endif]--> </head> <body bgcolor="#FFEFDB" lang=EN-US link="#0F0FCE" vlink="#19199E" style='tab-interval:.5in'> <div class=WordSection1> <p class=MsoNormal style='margin:0in;margin-bottom:.0001pt'><span style='color:black'><o:p>&nbsp;</o:p></span></p> <h2 align=center style='text-align:center'><span style='color:black'>COMPSCI 534.01: Computational Complexity<o:p></o:p></span></h2> <h2 align=center style='text-align:center'><span style='color:black'>Department of Computer Science<o:p></o:p></span></h2> <h2 align=center style='text-align:center'><span style='color:black'>Duke University<o:p></o:p></span></h2> <p class=MsoNormal align=center style='margin:0in;margin-bottom:.0001pt; text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt;mso-bidi-font-size:10.0pt;color:black'><a href="http://www.cs.duke.edu/~reif/"><span style='color:black'>John H. Reif</span></a> <o:p></o:p></span></b></p> <p class=MsoNormal align=center style='margin:0in;margin-bottom:.0001pt; text-align:center'><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt;mso-bidi-font-size:10.0pt;color:black'><br> &nbsp;&nbsp; Spring Semester, 2017 <o:p></o:p></span></b></p> <div class=MsoNormal align=center style='margin:0in;margin-bottom:.0001pt; text-align:center'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'> <hr size=2 width="100%" align=center> </span></div> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'><br> <b style='mso-bidi-font-weight:normal'>Instructor:<span style="mso-spacerun:yes"> </span></b><a href="http://www.cs.duke.edu/~reif/"><span style='color:black'>John H. Reif</span></a> <o:p></o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><span style='mso-tab-count:1'> </span>A. Hollis <span class=SpellE>Edens</span> Professor of Computer Science <o:p></o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><span style='mso-tab-count:1'> </span>Building: LSRC, Room: D106<o:p></o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><span style='mso-tab-count:1'> </span>E-mail: <span class=SpellE>reif</span> AT cs.duke.edu<o:p></o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><span style='mso-tab-count:1'> </span>Phone: 919-660-6568<o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Summary Description of Course: <o:p></o:p></span></b></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'>Computational Complexity is the study of bounds on the various metrics (such as time and space) of computations executed on abstract machine models (such as Turing machines, Boolean circuits)<span class=GramE>,,</span> required to solve given problems, as a function of the size of the problem input.<b style='mso-bidi-font-weight:normal'><o:p></o:p></b></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><b style='mso-bidi-font-weight: normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>Detailed Description of Course Material:</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'> see </span><b style='mso-bidi-font-weight: normal'><span style='font-size:14.0pt;mso-bidi-font-size:10.0pt;color:black'><a href="http://www.cs.duke.edu/courses/spring17/compsci534/lectures.htm">Schedule</a></span></b><span class=MsoHyperlink><span style='font-size:14.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Lectures:</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'><br> <br> <span class=GramE><span style="mso-spacerun:yes"> </span><b style='mso-bidi-font-weight: normal'><span style="mso-spacerun:yes"></span>Lecture</b></span><b style='mso-bidi-font-weight:normal'> Times:&nbsp;</b>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style='mso-tab-count:1'> </span>Tues, Thurs 11:45 PM  1:00 PM&nbsp;&nbsp; (See </span><b style='mso-bidi-font-weight:normal'><span style='font-size:14.0pt;mso-bidi-font-size:10.0pt;color:black'><a href="http://www.cs.duke.edu/courses/spring17/compsci534/lectures.htm">Schedule</a></span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'> for details)<br> <span style="mso-spacerun:yes"> </span><b style='mso-bidi-font-weight:normal'>Lecture Location: <span style='mso-tab-count:2'> </span></b>LSRC D106<o:p></o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><b style='mso-bidi-font-weight: normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>Reif Office Hours:&nbsp;&nbsp;</span></b><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <span style='mso-tab-count:2'> </span>Tues 1:00 PM  3:00 PM&nbsp;<br style='mso-special-character:line-break'> <![if !supportLineBreakNewLine]><br style='mso-special-character:line-break'> <![endif]><o:p></o:p></span></p> <p class=MsoNormal style='margin-left:.25in;mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><b style='mso-bidi-font-weight: normal'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>TA:</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'> </span><span style='font-size:12.0pt;mso-bidi-font-size:13.0pt;font-family:Arial;mso-bidi-language: EN-US'><a href="http://www.cs.duke.edu/people/graduate/?csid=567"><span class=SpellE><span style='font-family:Times'>Tianqi</span></span><span style='font-family:Times'> Song</span></a></span><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><o:p></o:p></span></p> <p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-pagination: none;mso-list:l4 level1 lfo1;tab-stops:28.0pt list .5in left 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><![if !supportLists]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:Symbol; mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>Office: 208 North Building<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-pagination: none;mso-list:l4 level1 lfo1;tab-stops:28.0pt list .5in left 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><![if !supportLists]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:Symbol; mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>Phone: 919-667-7346<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-pagination: none;mso-list:l4 level1 lfo1;tab-stops:28.0pt list .5in left 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><![if !supportLists]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:Symbol; mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'>TA email: </span><span class=SpellE><span style='font-size:12.0pt;mso-bidi-font-size:13.0pt; mso-bidi-font-family:Arial;mso-bidi-language:EN-US'>stq</span></span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'> AT cs.duke.edu<o:p></o:p></span></p> <p class=MsoNormal style='margin-left:.5in;text-indent:-.25in;mso-pagination: none;mso-list:l4 level1 lfo1;tab-stops:28.0pt list .5in left 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><![if !supportLists]><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;font-family:Symbol; mso-fareast-font-family:Symbol;mso-bidi-font-family:Symbol;color:black'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp; </span></span></span><![endif]><b style='mso-bidi-font-weight:normal'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'>TA office hours:</span></b><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'> To be determined<o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Required Text Books:</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'> <o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'>[Pap]&nbsp; Christos Papadimitriou. Computational Complexity. <i style='mso-bidi-font-style:normal'>Addison-Wesley Longman</i>, 1994. ISBN-10: 0201530821, ISBN-13: 978-0201530827. Corrections: <a href="http://www.cs.duke.edu/~reif/courses/complectures/books/P/PapadimitriouErrata.pdf">Errata</a>.<o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in;text-align:justify'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'>[<a href="http://www.cs.duke.edu/~reif/courses/complectures/books/AB/ABbook.pdf"><span style='color:black'>AB</span></a>] <a href="http://www.cs.princeton.edu/~arora/"><span class=SpellE><span style='color:black'>Sanjeev</span></span><span style='color:black'> <span class=SpellE>Arora</span></span></a> and <a href="http://www.cs.princeton.edu/~boaz/"><span style='color:black'>Boaz Barak</span></a>, <a href="http://www.cs.princeton.edu/theory/complexity/"><span style='color:black'>Computational Complexity: A Modern Approach</span></a>, </span><span style='font-size:12.0pt;mso-bidi-font-family:Arial;color:black;mso-bidi-language: EN-US'>Cambridge University Press (May 2009), ISBN: 978-0521424264</span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'><o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in;text-align:justify'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'>[<a href="http://www.cs.duke.edu/~reif/courses/complectures/books/G/Gbook.pdf"><span style='color:black'>G</span></a>] <a href="http://www.wisdom.weizmann.ac.il/~oded/"><span class=SpellE><span style='color:black'>Oded</span></span><span style='color:black'> <span class=SpellE>Goldreich</span></span></a>, <a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html"><span style='color:black'>Computational Complexity: A Conceptual Perspective</span></a>, </span><span style='font-size:12.0pt;mso-bidi-font-family:Arial;color:black; mso-bidi-language:EN-US'>Cambridge University Press, ISBN: 978-0521884730 (April 28, 2008)</span><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'><o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Additional Digital Text Books:</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'> ([<a href="http://www.cs.duke.edu/~reif/courses/complectures/books/AB/ABbook.pdf"><span style='color:black'>AB</span></a>] and [<a href="http://www.cs.duke.edu/~reif/courses/complectures/books/G/Gbook.pdf"><span style='color:black'>G</span></a>] used by permission)<o:p></o:p></span></p> <ul type=disc> <li class=MsoNormal style='color:black;mso-list:l1 level1 lfo2;tab-stops:list .5in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>Other <a href="http://www.cs.duke.edu/~reif/courses/complectures/books/references.html"><span style='color:black'>Relevant References</span></a> for Further Reading<o:p></o:p></span></li> </ul> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Surveys on Computational Complexity:<o:p></o:p></span></b></p> <ul style='margin-top:0in' type=disc> <li class=MsoNormal style='color:black;margin-top:0in;margin-bottom:12.0pt; mso-list:l5 level1 lfo3;tab-stops:list .5in'><span class=SpellE><span style='font-size:12.0pt;mso-bidi-font-size:1.0pt;mso-bidi-font-family: T2;mso-bidi-language:EN-US'>Oded</span></span><span style='font-size:12.0pt; mso-bidi-font-size:1.0pt;mso-bidi-font-family:T2;mso-bidi-language:EN-US'> <span class=SpellE>Goldreich</span>, </span><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><a href="http://www.cs.duke.edu/~reif/courses/complectures/surveys/Goldreich.pdf"><span style='color:black'>Computational Complexity</span></a>, 2000<o:p></o:p></span></li> <li class=MsoNormal style='color:black;margin-top:0in;margin-bottom:12.0pt; mso-list:l5 level1 lfo3;tab-stops:list .5in'><span class=SpellE><span style='font-size:12.0pt;mso-bidi-font-size:1.0pt;mso-bidi-font-family: T2;mso-bidi-language:EN-US'>Oded</span></span><span style='font-size:12.0pt; mso-bidi-font-size:1.0pt;mso-bidi-font-family:T2;mso-bidi-language:EN-US'> <span class=SpellE>Goldreich</span> and <span class=SpellE>Avi</span> <span class=SpellE>Wigderson</span>, </span><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt'><a href="http://www.cs.duke.edu/~reif/courses/complectures/surveys/GoldreichWigderson.pdf"><span style='color:black'>Computational Complexity</span></a>, Oct 2004 <o:p></o:p></span></li> </ul> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;mso-bidi-font-size:10.0pt;color:black'>Prerequisites:</span></b><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt;color:black'><br> <br> There are no formal prerequisites for the course, except mathematical maturity.&nbsp; However, it would help to have a working knowledge of Turing Machines, NP-Completeness, and Reductions, at the level of an undergraduate algorithms class. <br> <br> <b style='mso-bidi-font-weight:normal'>Topics: see above Schedule<o:p></o:p></b></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><b style='mso-bidi-font-weight:normal'><span style='font-size: 12.0pt;color:black'>Grading:</span></b><span style='font-size:12.0pt; color:black'><br> <br> </span><span style='font-size:12.0pt;mso-bidi-font-family:Times;color:black'>There will be 5 <span class=SpellE>homeworks</span> (5% each, 25% total), two quizzes (7.5% each), a midterm exam (10%), an end-term Final Exam (20%), and a Final Project&nbsp; (25%) for the course.&nbsp; Also attendance and class interaction will provide an additional 5% of the total grade.</span><span style='font-size: 12.0pt;color:black'><o:p></o:p></span></p> <p class=Default style='margin-bottom:12.15pt;text-align:justify;line-height: 12.0pt'><span class=SpellE><b style='mso-bidi-font-weight:normal'>Homeworks</b></span><b style='mso-bidi-font-weight:normal'>:</b><span style="mso-spacerun:yes"> </span>To be prepared using LATEX (preferred) or WORD. </p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;line-height:12.0pt'><i style='mso-bidi-font-style: normal'>Homework Rules:<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.75in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l0 level1 lfo5;tab-stops:list .75in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>Be sure to provide enough details to convince me, but try to keep your answers to at most one or two pages.<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.75in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l0 level1 lfo5;tab-stops:list .75in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>It is OK to answer a problem by stating it is open, but if so, please convincingly explain the reasons you believe this.<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.75in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l0 level1 lfo5;tab-stops:list .75in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>It is permitted to collaborate with your classmates, but please list your collaborators with your homework solution.<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.75in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l0 level1 lfo5;tab-stops:list .75in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>There is no credit given for homework past their due date.<o:p></o:p></i></p> <p class=Default style='margin-bottom:12.15pt;text-align:justify;line-height: 12.0pt'><b style='mso-bidi-font-weight:normal'>Final Project:</b> </p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l2 level1 lfo6;tab-stops:list .5in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>The final project is a short (approx. 12 pages) paper over viewing (definition of the problem and terminology, and the details of some part of the proof) a prior result in complexity theory.<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l2 level1 lfo6;tab-stops:list .5in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>The topic is of your choice, and the instructor will provide guidance on relevant literature. <o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;text-indent:-.25in;line-height:12.0pt; mso-list:l2 level1 lfo6;tab-stops:list .5in'><![if !supportLists]><span style='font-family:Symbol;mso-fareast-font-family:Symbol;mso-bidi-font-family: Symbol'><span style='mso-list:Ignore'><span style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span></span><![endif]><i style='mso-bidi-font-style:normal'>Novel topics and/or new research may result, but is not necessarily required to still produce an excellent project paper.<o:p></o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;text-indent:.5in;line-height:12.0pt'><i style='mso-bidi-font-style:normal'><o:p>&nbsp;</o:p></i></p> <p class=Default style='margin-top:0in;margin-right:0in;margin-bottom:12.15pt; margin-left:.5in;text-align:justify;text-indent:.5in;line-height:12.0pt'><i style='mso-bidi-font-style:normal'><o:p>&nbsp;</o:p></i></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in;text-indent:.5in'><span style='font-size:12.0pt;mso-bidi-font-size: 10.0pt;color:black'><o:p>&nbsp;</o:p></span></p> <p class=MsoNormal style='mso-pagination:none;tab-stops:28.0pt 56.0pt 84.0pt 112.0pt 140.0pt 168.0pt 196.0pt 224.0pt 3.5in 280.0pt 308.0pt 336.0pt; mso-layout-grid-align:none;text-autospace:none'><span style='font-size:12.0pt; mso-bidi-font-size:10.0pt;color:black'><span style="mso-spacerun:yes"></span><o:p></o:p></span></p> <p class=MsoNormal style='margin-top:0in;margin-right:0in;margin-bottom:12.0pt; margin-left:0in'><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt; color:black'><o:p>&nbsp;</o:p></span></p> <p><span style='mso-fareast-font-family:"Times New Roman";color:black'><o:p>&nbsp;</o:p></span></p> </div> </body> </html>