CMSC858M: Algorithmic Lower Bounds: Fun with Hardness Proofs, Spring 2019

 

Prof. Mohammad T. HajiAghayi

 

See also the sister course to this course at MIT by Prof. Erik Demaine taught simultaneously.

 

Latest Announcements

·      Exam date: TBD (in the class)

·      Topics of the projects should be checked with the instructor and finalized by Feb 28, 2019

·      See the poster prepared by Erik Demaine for the sister course.

·      See the course agenda

·         First lecture on January 29, 2019 at CSI 3118

·        Templates .tex .sty to scribe

 

Assignments due at the beginning of the class on due dates

 

Google page for reporting on projects

 

Course Description

 

Algorithms are used everywhere and lots of people design Algorithms for different settings. However sometime we cannot design algorithms with certain efficiency in time, space, approximation, etc. In this course we want to understand why this happens. We also consider the common techniques to prove hardness of algorithms for different settings. In short, while in typical advanced algorithm courses we learn design of algorithms for different settings, in this course we learn why we cannot design algorithms with certain guarantees in different settings. Though we mention and prove several complexity results in this course, the focus of the course is still on algorithms.

 

To the best of our knowledge this is the first course by Erik Demaine at MIT and myself ever taught on algorithmic lower bounds. Though we co-teach this course the lectures are taught separately. See here for the MIT course.

 

Course Agenda:

           

            See the course agenda.

 

 

            Course Topics (Tentative):

·        NP-completeness

o   3SAT and all its variations

o   3-partition

o   Hamiltonicity

o   2D/3D geometric problems

·        PSPACE, EXPTIME, EXPSPACE

·        Games, Puzzles, and Computation

o   Tetris

o   Nintendo games: Super Mario Bros., The Legend of Zelda, Metroid, Pokémon, ...

o   Sliding blocks and Rush Hour

o   Constraint Logic

o   Sudoku and other Nikoli pencil-and-paper games

o   Chess, Go, Othello, and other board games

·        Inapproximability

o   PCP theorem and OPT-preserving reductions

o   APX-hardness (e.g., Vertex Cover)

o   Set-cover hardness

o   Group Steiner tree

o   k-dense subgraph

o   Label cover hardness

o   Unique Games Conjecture (UGC)

o   Independent set

·        Fixed-parameter intractability

o   Parameter-preserving reductions

o   W hierarchy

o   Clique-hardness and ETH hardness

o   Kernelization hardness

·        3SUM-hardness (n2 and the Exponential Time Hypothesis)

·        All-pair shortest path hardness (subcubic reduction)

·        Counting problems (#P)

·        Solution uniqueness (ASP)

·        Game theory (PPAD)

·        Hardness for Online Algorithms

·        Hardness for Streaming Algorithms (Index, Set Disjointness)

·        Existential theory of the reals

·        Undecidability

Schedule and Materials (in order):

 

Review of course description, motivation for the course and its topics

Scanned handwritten notes

Scribe notes by students

 

Introduction and review of complexity theory: P, NP, EXP, PSPACE

Scanned handwritten notes

Scribe notes by students

 

NP-completeness proofs: reductions from 3-Partition

Scanned handwritten notes

Scribe notes by students

 

Cubic hardness and all-pair shortest paths

Scanned handwritten notes

Scribe notes by students

 

Quadratic hardness and 3-SUM

Scanned handwritten notes

Scribe notes by students

 

3-SAT and NP-hardness proofs

Scanned handwritten notes

Scribe notes by students

 

Further NP-hardness and ways to cope with NP-hardness

Scanned handwritten notes  (combined notes with the previous session)

Scribe notes by students (combined scribe notes with the previous session)                                                                      

 

Different levels of inapproximability for minimizing problems

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Different levels of inapproximability for maximizing problems

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

Approximation-preserving and gap-preserving reductions, PCP theorems

Scanned handwritten notes (combined notes)

Scribe notes by students

 

More examples of approximation-preserving and gap-preserving reductions

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

APX-hardness proofs via gap-preserving reductions

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Gap amplification, integrality gap, and unique-game conjecture Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

Introduction to fixed-parameter tractability

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Parameterized reductions and assumptions

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

W-hardness hierarchy and weighted circuit satisfiability

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Further parameterized reductions and hardness for kernels, connection to other fields of algorithms

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

Introduction to online algorithms and lower bounds for paging

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Lower bounds for online matching and online set cover

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

Introduction to streaming algorithms: INDEX and DISJOINTNESS tools for lower bounds

Scanned handwritten notes (combined notes)

Scribe notes by students

 

Several examples of streaming algorithm lower bounds

Scanned handwritten notes (combined notes)

Scribe notes by students (combined scribe notes with the previous session)

 

Algorithmic game theory lower bounds and PPAD-completeness

Scanned handwritten notes

Scribe notes by students

 

List of projects (example from the past)

 

Title

Members

Slides

Scribes

Hardness of Facility Location Problems

Karthik Abinav S, Thomas Pensyl

Slides

Scribes

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

References and resources

 

There is no textbook for this class, but there are two recommended books and several useful websites.

1.     Computers and Intractability A Guide to the Theory of NP-Completeness: book by Michael R. Garey and David S. Johnson

2.     Johnson's followup NP-completeness Columns

3.     Games, Puzzles, & Computation: book by Robert A. Hearn and Erik D. Demaine

4.     Complexity Zoo

5.     A compendium of NP optimization problems

Prerequisites

 

Though there is no official prerequisites for this course already passing a course in (advanced) algorithms is very important for this course. If you are unsure of whether you have sufficient background for this course or not, please e-mail the instructor in the first week of the class or before.

 

Tentative Grading & Evaluation

 

See the course agenda for details.

 

History

 

This is a brand new class. Help shape it with your feedback and content requests!

 

 

            Other Resources (from here)

 

            Tips for good technical writing

           The elements of style by William Strunk Jr. and E. B. White (follow the "External links" at the bottom of this page for online copies of this book).

           Writing a technical paper, by Professor Michael Ernst.

                 Tips for writing technical papers, by Professor Jennifer Widom.

           Writing suggestions, by Professor Barton Miller.

           How to write a dissertation, by Professor Douglas Comer (most of the content on this page applies to all forms of technical writing).

 

            Tips for effective presentation

           Giving a technical talk, by Professor Michael Ernst.

           Tips for a good conference talk, by Professor Jennifer Widom.

           Oral presentation advice, by Professor Mark Hill.

 

General Information

Instructor:

Mohammad T. HajiAghayi

Lectures:

TuTh 3:30pm-4:45pm

Location:

CSI 3118

Office hours:      

By appointment via e-mail OR the hour immediately following class.

Office:

A.V. Williams Bldg., Room 2113

Email:

The first 8 letters of instructor’s last name (AT) cs (DOT) umd (DOT)  edu