CS5200 Approximation Algorithms (Jan- April 2025)

# CS5200 Approximation Algorithms (Jan- April 2025) ### Jan - May 2025, CSE IITH --- ## Logistics * **Instructor**: Dr. Subrahmanyam Kalyanasundaram, CSE Department * **Course code and name**: CS5200, Approximation Algorithms * **Lecture timings**: P-slot (Mon 14:30-16:00 and Thu 16:00-17:30) * **Location**: CS-LH1 * **Office Hours**: Fix an appointment over email * **Teaching Assistant**: Subham Bhattacharjee (email:cs23resch01002@iith) ## Course Overview Many optimization problems have been proven to be NP hard, and hence we do not have efficient algorithms. One approach to address this is the area of approximation algorithms, where one obtains algorithms which are guaranteed to be close to the optimal solution. During the course, we will look at the motivation, various types of algorithms and different techniques to design and analyze approximation algorithms. We will focus on approximation algorithms with provable guarantees. Hence there should be a strong mathematical maturity and familiarity with theorems and proofs. Students should have familiarity with undergraduate algorithms. ## List of topics * Introduction to approximation algorithms * Greedy algorithms * Local search techniques * Randomized Algorithms * Basics of Linear Programming and its application to Approximation Algorithms * LP Relaxation, Integrality Gap * Deterministic Rounding * Randomized Rounding * Primal-Dual Method * Semidefinite Programming We will cover most of these topics during the course. ## Resources Please find below two textbooks and many lecture notes/course webpages from other universities where a similar course have been offered. #### Textbooks * Approximation Algorithms by Vijay Vazirani, 2001. A soft copy is [available](https://ics.uci.edu/~vazirani/book.pdf) in the author's homepage. * Design of Approximation Algorithms by David Williamson and David Shmoys, 2011. A soft copy is available at [this website](https://www.designofapproxalgs.com/). * For Linear Programming, you can refer to Understanding and Using Linear Programming by Jiří Matoušek and Bernd Gärtner. A soft copy is available at [this website](https://blogs.epfl.ch/extrema/documents/Maison%2020.05.10.pdf). * For Linear Programming, another great book is Introduction to Linear Optimization by Dmitris Bertsimas and John Tsitsiklis. Details available [here](http://athenasc.com/linoptbook.html) though I could not find an official soft copy online. * For Semidefinite Programming a good book is Approximation Algorithms and Semidefinite Programming by Jiří Matoušek and Bernd Gärtner. You may find a soft copy online. #### Other courses on approximation algorithms and lecture notes * Course at IISc by Arindam Khan and Anand Louis: [Website](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/ApproxAlgo.html) * Notes by Deeparnab Chakrabarty: [Website](https://www.cs.dartmouth.edu/~deepc/appx-lecture-notes.htm) * NPTEL Course by Palash Dey: [Website](https://onlinecourses.nptel.ac.in/noc24_cs97/preview) * Course at CMU by Anupam Gupta and R Ravi: [Website](http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/) * Course at JHU by Michael Dinitz: [Website](https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2021/) * Course at TU Munich by Jannik Matuschke: [Website](https://www.ot.mgt.tum.de/en/or/teaching/winter2018/approxalgorithms/) * Course at UIUC by Chandra Chekuri: [Website](https://courses.grainger.illinois.edu/cs583/fa2021/) * Notes by Rajeev Motwani: [Website](http://i.stanford.edu/pub/cstr/reports/cs/tr/92/1435/CS-TR-92-1435.pdf) ## Evaluation Scheme Here is a tentative scheme that we will follow: - 3 In-class exams (55%) split as 17% (exam 1) - 17% (exam 2) - 21% (final exam) - Tentative date for exam 1: February 27th - Tentative date for exam 2: March 27th - Tentative date for final exam: May 1st - Homework Assignments (25%) - Scribe Notes (15%) - Class participation (5%) **Important Note:** Academic integrity is very important. In the homework assignments, you may discuss with others, but the final submissions are to be in entirely your own words. If you have discussed with others, and/or referred to resources, please cite them clearly at the beginning of your submission. If any submission is found to be plagiarized, appropriate penalties may apply. The same applies for scribe notes. The submissions should be your own work. ## Lecture Schedule * Lecture 1: 2 January, 2025 - Introduction to Approximation Algorithms - Overview of the course, logistics - Motivation and definition of approximation algorithm - Vertex Cover algorithm using maximal matching - Tight example - Sources: Chapter 1 of Vijay Vazirani's book. - References: [Avrim Blum](https://www.cs.cmu.edu/~avrim/451f12/lectures/lect1106.pdf), [Dave Mount](https://www.cs.umd.edu/class/fall2017/cmsc451-0101/Lects/lect22-apx-vc-tsp.pdf), [Michael Dinitz](https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2019/Lectures/lecture1.pdf) * Lecture 2: 6 January, 2025 - Set Cover, Problem Statement - Greedy algorithm which provides $O(\log n)$ approximation - Tight example - Sources: Chapter 2 of Vijay Vazirani's book, Section 1.6 of Williamson-Shmoys' book. - References: [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/handwritten/hand_w1l2.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/1.%20Greedy%20Algorithm%20for%20Set%20Cover.pdf), [Michael Dinitz](https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2019/Lectures/lecture3.pdf) * Lecture 3: 9 January, 2025 - Travelling Salesman Problem - Hardness for general case - 2 approximation algorithm (double tree) - $3/2$ approximation algorithm by Christofedes - Tight example - Sources: Chapter 3 of Vazirani, [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/handwritten/hand_w2.pdf), Section 2.4 of Williamson and Shmoys, [Notes from MIT](https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/6b105f245cf0048b2d943219006f0f72_MIT15_083JF09_lec22.pdf) * Lecture 4: 13 January, 2025 * Knapsack * Notion of FPTAS * FPTAS for knapsack * Scribe: Suryaansh? * Sources: Chapter 8 of Vazirani, Section 3.1 of Williamson and Shmoys, [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/handwritten/hand_w2.pdf), [Anupam Gupta](https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf) * Lecture 5: 16 January, 2025 * Minimum Makespan Scheduling * Factor 2 algorithm and tight example * List scheduling algorithm and analysis of $3/2$ approximation factor * Overview of PTAS * Exercise: 4/3 analysis of list scheduling * Scribe: Varun?? * Sources: Chapter 10 of Vazirani, Section 2.3 of Williamson and Shmoys, [Ola Svensson](https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture2.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/3.%20PTAS%20for%20Load%20Balancing.pdf), [Zachary Friggstad](https://webdocs.cs.ualberta.ca/~zacharyf/courses/approx_2014/notes/sep17-675.pdf) * Lecture 6: 23 January, 2025 - PTAS for Makespan Scheduling - Divide into big jobs and small jobs, Dynamic Programming for big jobs, and greedy scheduling for small jobs - MAX-CUT local search algorithm - Local Search algorithm for both unweighted and weighted cases - Exercises: Tight example for $4/3$ approximation in greedy scheduling - Scribe: Anshul?? - Sources: Chapter 10 of Vazirani, Section 3.2 of Williamson and Shmoys, [Ola Svensson](https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture2.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/3.%20PTAS%20for%20Load%20Balancing.pdf), [Zachary Friggstad](https://webdocs.cs.ualberta.ca/~zacharyf/courses/approx_2014/notes/sep17-675.pdf), [Notes from Univ of Freiburg](https://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/makespan_scheduling.pdf) * Lecture 7: 27 January, 2025 - Randomized Approximation Algorithm for MAX-CUT - Derandomization using the method of conditional expectations - Greedy interpretation of Derandomized Algorithm - Local search $2/3$ approximation algorithm MAX-2-SAT - Exercises: Improve/analyze the $3/4$ approximation algorithm for MAX-2-SAT - Scribe: Muskan?? - Sources: [Anna Karlin](https://courses.cs.washington.edu/courses/cse525/13sp/scribe/lec2.pdf), [Deeparnab Chakrabarty for MAX-2-SAT](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/2a.%20Non-Oblivious%20Local%20Search.pdf), [Deeparnab Chakrabarty for MAX-CUT](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/2.%20Local%20Search%20Algorithms.pdf), [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/handwritten/hand_w1l2.pdf) * Lecture 8: 30 January, 2025 - Introduction to Linear Programming - Representing Vertex Cover as an Integer Linear Program - LP Relaxation and Rounding - Integrality Gap of Vertex Cover LP - Exercises: Show that the integrality gap is close to 2, even after the addition of triangle constraints. - Scribe: Yash?? - Sources: [Ola Svensson](https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/4.%20Linear%20Programming%20Relaxations.pdf), [Chandra Chekuri](https://courses.grainger.illinois.edu/cs598csc/sp2011/Lectures/lecture_4.pdf), [Kamesh Munagala](https://users.cs.duke.edu/~kamesh/APPROX/lec10.pdf). * Lecture 9: 3 February, 2025 (by Rakesh Venkat) - LP based $O(\log n)$ algorithm for Set Cover - Randomized Rounding - Scribe: - Sources: Chapter 14 of Vazirani, [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/7.%20Randomized%20Rounding.pdf), [Ola Svensson](https://theory.epfl.ch/osven/courses/Approx13/Notes/lecture6.pdf), [Anupam Gupta](https://www.cs.cmu.edu/~anupamg/adv-approx/lecture2.pdf), Section 1.7 of Williamson and Shmoys, [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/scribes/scribe_w4.pdf) * Lecture 10: 6 February, 2025 - $3/4$ Approximation Algorithm for MAX-SAT - $(1- 1/e)$ Approximation using randomized rounding the LP relaxation - Combining randomized rounding and random assignment to obtain a $3/4$ approximation - Scribe: Ayush - Sources: Chapter 16 of Vazirani, Sections 5.3, 5.4 and 5.5 of Williamson and Shmoys, [Avrim Blum](https://www.cs.cmu.edu/~avrim/Randalgs11/lectures/avrim-maxsat.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/7b.%20Randomized%20Rounding%20for%20Max%20Sat.pdf) * Lecture 11: 10 February, 2025 (by Rogers Mathew) - Greedy $1/3$ approximation for hypergraph matching in 3-uniform hypergraphs. - Exercise: Extend this algorithm for the case when hyperedges have weights. - Lossless rounding for weighted bipartite matching. - Scribe: - Sources: [Deeparnab Chakrabarty 1](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/4b.%20Hypergraph%20Matching.pdf), [Deeparnab Chakrabarty 2](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/6.%20Deterministic%20Rounding%20for%20Generalized%20Assignment%20Problem.pdf), [A. A. Ahmadi](http://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf), [Michel Goemans](https://math.mit.edu/~goemans/18433S09/matching-notes.pdf) * Lecture 12: 13 February, 2025 - Introduction to the geometry of linear programs and polyhedra - Vertices, Extreme Points and Basic Feasible Solutions and their equivalence - If $P$ has no line (equivalently contains a basic feasible solution), then there exists an optimal solution that is a basic feasible solution. - Sources: Chapter 2 of Bertsimas and Tsitsiklis, [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/4a.%20Crash%20Course%20on%20Linear%20Programming.pdf) * Lecture 13: 17 February, 2025 - $3/7$ approximation algorithm for hypergraph matching in 3-uniform hypergraphs. - Example that shows integrality gap of $3/7$. - Exercise: Generalize this to $(k+ \frac{1}{k} - 1)^{-1}$ approximation for $k$-uniform hypergraphs. - Sources: [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/4b.%20Hypergraph%20Matching.pdf), (paid link for) [original paper](https://link.springer.com/article/10.1007/BF01303202) by Füredi, Kahn and Seymour, [follow up paper](https://cs.uwaterloo.ca/~lapchi/papers/hypergraph-conf.pdf) by Chan and Lau. * Lecture 14: 20 February, 2025 - LP Duality - Weak Duality - Complementary Slackness - Exercise: Directly derive the dual of the LP $\min \mathbf c\cdot \mathbf x$ subject to the following constraints: $$ A \mathbf x = \mathbf b, \text{ and } \mathbf x \geq \mathbf 0.$$ Interpret weak duality in this form similar to the way we reasoned about the LP form in class. - Sources: Chapter 12 of Vazirani, Chapter 6 of Matoušek and Gärtner. [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/8a.%20Crash%20Course%20on%20Linear%20Programming%20-%20part%202.pdf), [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/handwritten/hand_w3.pdf) * Lecture 15: 24 February, 2025 - General form of LP and its dual form - Proof of Strong Duality theorem assuming Separating Hyperplane theorem - Farkas Lemma - Exercise: Prove the equivalence of different forms of Farkas Lemma - Sources: [A. A. Ahmadi](https://www.princeton.edu/~aaa/Public/Teaching/ORF523/S16/ORF523_S16_Lec5_gh.pdf), [David Williamson 1](https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec07.pdf), [David Williamson 2](https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec08.pdf), [Video of David Karger](https://www.youtube.com/watch?v=ooxbRb5oJow), Chapter 6 of Matoušek and Gärtner, Chapter 4 of Bertsimas and Tsitsiklis, [Rajat Mittal](https://www.cse.iitk.ac.in/users/rmittal/prev_course/s14/notes/lec6.pdf). * Lecture 16: 3 March, 2025 - Primal Dual Method - Primal Dual Method applied to Set Cover to yield an $f$ approximation algorithm - Primal Dual Algorithm for Feedback Vertex Cover - Simplifications of the graph yielding a graph with a short cycle (length at most $4 \log n$) - Sources: Chapter 15 of Vazirani, Sections 7.1 and 7.2 of Williamson-Shmoys, [University of Freiburg](https://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/set_cover.pdf), [Michael Dinitz](https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2019/Lectures/lecture20.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/8.%20LP%20Duality%20-%20Set%20Cover%20and%20Vertex%20Cover.pdf), * Lecture 17: 6 March, 2025 * General Template of Primal Dual Method * Relaxed Complementary Slackness Conditions * Primal Dual Algorithm for Feedback Vertex Cover * Set Cover Integrality Gap * Sources: Chapter 15 of Vazirani, Sections 7.1 and 7.2 of Williamson-Shmoys, [Thatchaphol Saranurak](https://www.dropbox.com/scl/fo/y5x5rbqbih6wlvn7w0qt1/AJV3t3Kz0BAE4FX3BLAnhJ0?e=2&preview=l10_2_approx_PrimalDual.pdf&rlkey=23od60wq2eagu2vj6syn7h4hy&dl=0), [Video by Thatchaphol Saranurak](https://www.youtube.com/watch?v=Pmv1rE3yXOs), [Arindam Khan](https://www.csa.iisc.ac.in/~arindamkhan/courses/ApproxAlgo22/scribes/scribe_w4.pdf) * Lecture 18: 17 March, 2025 * Shortest Path Problem seen in the Primal Dual Framework * Exact Algorithm * Sources: [Rohit Gurjar](https://www.cse.iitb.ac.in/~rgurjar/CS602_2022/Slides/PrimalDual.pdf), [Video by Rohit Gurjar](https://drive.google.com/file/d/1I944e9HYQOWB0FprS8oGMvuiqW3O6vp1/view?usp=sharing), [Sundar Vishwanathan](https://www.cse.iitb.ac.in/~sundar/cs435/lecture22.pdf), [Video by David Karger](https://www.youtube.com/watch?v=vdO4zQSEnok), A slightly different approach in Section 7.3 of Williamson-Shmoys. * Lecture 19: 20 March, 2025 * Introduction to Semidefinite Programming * Basic form, How we can solve SDPs * Positive Semidefinite matrices and different characterizations * Sources: [Jaikumar Radhakrishnan](https://www.tcs.tifr.res.in/~kavitha/11-Lecture-01-Mar-2022.pdf), [Video by Jaikumar Radhakrishnan](https://www.youtube.com/watch?v=2TwW_Axyx1s), [Slides by Bernd Sturmfels](https://www.aimath.org/WWN/convexalggeom/AIM.pdf), [Notes on PSD Matrices by Matt Devos](https://www.sfu.ca/~mdevos/notes/semidef/semidef_mat.pdf), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/11a.%20Semidefinite%20Programming.pdf) * Lecture 20: 24 March, 2025 * 0.878 Approximation Algorithm for Max-Cut using SDPs by Goemans and Williamson * SDP Integrality Gap for Max-Cut * Approximation Algorithm for MAX-2-SAT * Sources: Chapter 26 of Vazirani, Chapter 6 of Williamson-Shmoys, [Chapter 1 of Matousek-Gartner SDP book](https://ti.inf.ethz.ch/ew/lehre/ApproxSDP09/notes/maxcut.pdf), [Tim Roughgarden](https://timroughgarden.org/w16/l/l20.pdf), [Zachary Friggstad](https://webdocs.cs.ualberta.ca/~zacharyf/courses/approx_2014/notes/oct24-675.pdf), [Video by Rohit Gurjar](https://drive.google.com/file/d/1nlxA6jFYDqv8q9J_oAr0_2mB5NwOSV2a/view), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/11b.%20SDP%20-%20Goemans-Williamson.pdf) * Lecture 21: 3 April, 2025 * Lovasz Theta function * Connection to $\alpha(G)$ and $\chi(\overline{G})$ * Shannon Capacity of $C_5$ * Sources: Chapter 3 of Matoušek and Gärtner book on SDPs, [Jaikumar Radhakrishnan](https://www.tcs.tifr.res.in/~kavitha/12-Lecture-03-Mar-2022.pdf), [Video by Jaikumar Radhakrishnan](https://www.youtube.com/watch?v=-3EoyfY0ldA), [Rajat Mittal](https://www.cse.iitk.ac.in/users/rmittal/prev_course/s14/notes/lec18.pdf) * Lecture 22: 7 April, 2025 * Computing Shannon Capacity of $C_5$ using Lovasz Theta Function * SDP formulation of Lovasz Theta Function * Sources: Chapter 3 of Matoušek and Gärtner book on SDPs, [Jaikumar Radhakrishnan](https://www.tcs.tifr.res.in/~kavitha/12-Lecture-03-Mar-2022.pdf), [Video by Jaikumar Radhakrishnan](https://www.youtube.com/watch?v=-3EoyfY0ldA), [Matt Devos](https://www.sfu.ca/~mdevos/notes/semidef/theta.pdf) * Lecture 23: 17 April, 2025 * Coloring 3 colorable graphs * Wigderson's algorithm that uses $O(\sqrt n)$ colors * Karger-Motwani-Sudan algorithm which uses SDP rounding and Wigderson's algorithm resulting in $\widetilde O(n^{0.25})$ colors * Sources: Chapter 9 of of Matoušek and Gärtner book on SDPs, Section 13.2 of Williamson-Shmoys, [Jaikumar Radhakrishnan](https://www.tcs.tifr.res.in/~kavitha/13-Lecture-08-Mar-2022.pdf), [Video by Jaikumar Radhakrishnan](https://www.youtube.com/watch?v=dYMkykfP2uE), [Video by Rakesh Venkat](https://www.youtube.com/watch?v=5F3oxsDBoW4), [Deeparnab Chakrabarty](https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/11c.%20SDP%20-%20Karger-Motwani-Sudan.pdf), [Paper by Karger Motwani Sudan](https://arxiv.org/abs/cs/9812008), [Notes from a course of Sushant Sachdeva](https://sachdevasushant.github.io/courses/15s-cpsc665/presentations/charles-coloring.pdf) * Lecture 24: 21 April, 2025 * Coloring 3 colorable graphs using $\widetilde O(n^{0.25})$ colors * Introduction to hardness of approximation * Gap introducing and gap preserving reductions * Sources: Refer to Lecture 23 for sources for coloring 3 colorable graphs. [Prahladh Harsha 23](https://www.tcs.tifr.res.in/~prahladh/teaching/2022-23/pcps/notes/01-20230127-fglss.pdf), Section 16.3 of Williamson-Shmoys, Chapter 29 of Vazirani, [Prahladh Harsha 07](https://www.tcs.tifr.res.in/~prahladh/teaching/07autumn/lectures/lec1-notes.pdf), [Slides by Nabil Mustafa](https://lipn.univ-paris13.fr/~mustafa/TechnicalWritings/Complexityslides/lec19.pdf) * Lecture 25: 24 April, 2025 * Introduction to PCP * Two characterizations of PCP theorem: * Probabilistically checkable proofs * GAP MAX-3SAT * Equivalence of the above characterizations * Sources: [Prahladh Harsha 23](https://www.tcs.tifr.res.in/~prahladh/teaching/2022-23/pcps/notes/01-20230127-fglss.pdf), [Video by Prahladh Harsha](https://www.youtube.com/watch?v=qcnIi1bxQhI), Section 16.3 of Williamson-Shmoys, Chapter 29 of Vazirani, [Write up by Ryan O'Donnell on the history of PCP Theorem](https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf) * Lecture 26: 28 April, 2025 * Hardness of Max-CLIQUE -- FGLSS * Direct reduction from PCP to obtain arbitrary constant factor inapproximability * Sources: [Prahladh Harsha 23](https://www.tcs.tifr.res.in/~prahladh/teaching/2022-23/pcps/notes/01-20230127-fglss.pdf), [Video by Prahladh Harsha](https://www.youtube.com/watch?v=qcnIi1bxQhI), Section 16.3 of Williamson-Shmoys, Chapter 29 of Vazirani, [Original Paper by FGLSS](https://www.cs.umd.edu/~gasarch/TOPICS/pcp/fglss.pdf), [Venkat Guruswami and Ryan O'Donnell](https://courses.cs.washington.edu/courses/cse533/05au/lecture10.pdf)