Algorithmic Lower Bounds: Fun with Hardness Proofs

In this video, the instructor describes the optional problem-solving sessions associated with the course. He suggests that these sessions provide an opportunity for students to advance the field and to develop a sense of camaraderie with one another.

In this video, the instructor shares his approach for helping students move forward when they get stuck during problem solving.

In this video, the instructor discusses the rationale behind his pedagogical decision to have students to scribe lecture notes. He also shares his insights about providing feedback on students' written notes.

In this video, the instructor discusses the final projects in the course, including the purpose of the projects, how students approach them collaboratively, students' presentations of their projects, and the feedback he provides.

In this video, the instructor discusses how he administered a survey to learn about students' backgrounds and interests coming in to the class, and how he used the results to refine the course design.

In this video, the instructor shares why he developed this course about hardness proofs and what makes it unique.

In this video, the instructor discusses the role of fun in research, teaching and learning. He shares that fun often makes problems accessible and provides an entryway for students into hardness proofs.

In this video, the instructor shares what he would do differently if he were to teach the course again, including spotlighting some of the more interesting subtopics within the vast field of approximation algorithms.

In this lecture, Professor Demaine continues deriving strong NP-hardness reductions from 3-partition, and weak NP-hardness reductions from 2-partition.

In this lecture, Professor Demaine explains hardness of problems that can be solved in polynomial time, but where that polynomial seems to be substantially superlinear.

In this lecture, Professor Demaine gives examples of real bounded games proved PSPACE-complete via constraint logic.

In this lecture, Professor Demaine describes counting versions of NP problems.

In the second of two guest lectures by Prof. Constantinos Daskalakis of CSAIL, Daskalakis talks about examples of PPAD-completeness reductions, as well as other classes related to PPAD.

In this first of two guest lectures by Prof. Constantinos Daskalakis of CSAIL, Daskalakis talks about the class PPAD, illustrating connections to economic game theory, topology, and graph theory.

In this lecture, Professor Demaine explains P-completeness, and how it can be undecidable to determine winning strategies in games.

In this lecture, Professor Demaine introduces planar versions of 3SAT, proving these versions are NP-hard.

In this lecture, Professor Demaine begins a series on inapproximability, proving the impossibility of approximation algorithms.

In this lecture, Professor Demaine proves hardness for game with fewer or more than one player.

In this lecture, Professor Demaine explains gap problems, using the PCP theorem.

In this lecture, Professor Demaine explains the concept of circuit SAT.

In this lecture, Professor Demaine describes constraint logic.

In this lecture, Professor Demaine proves the NP-hardess of various video games.

In this lecture, Professor Demaine explains L-reductions to prove various problems APX-complete, introduces a characterization theorem for approximability, and mentions the approximation spectrum.

In this lecture, Professor Demaine describes strong bounds on running time, assuming the Exponential Time Hypothesis.

In this lecture, Professor Demaine begins his analysis of decision problems from a parameterized perspective, as well as defining the general W hierarchy.

In this lecture, Professor Demaine finishes up NP-hardness, and the various techniques involved in such proofs.

In this lecture, Professor Demaine introduces Hamiltonicity.

In this lecture, Professor Demaine explains hardness proofs of games and puzzles, and graph theoretic problems, all reducing from 3-SAT.

In this lecture, Professor Demaine starts a series of lectures on satisfiability, including using SAT to prove NP-hardness.

In this lecture, Professor Demaine introduces the concept of 3-partition and its many variations, a starting point for NP-hardness reductions. Weak and strong NP-hardness proofs are seen in the context of other examples.

In this lecture, Professor Demaine gives a brief overview of the class, summarizing the prerequisite complexity theory and featuring two examples of hardness proofs in games.