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
·
Homework 3
due TBD in my mailbox of the first floor of A.V. Williams.
·
Homework
2 due TBD in my mailbox of the first floor of A.V. Williams.
·
Homework
1 due TBD in my mailbox of the first floor of A.V. Williams.
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 coteach this course the lectures are taught separately. See here for the MIT course.
Course Agenda:
See the course
agenda.
Course Topics (Tentative):
·
NPcompleteness
o 3SAT and all its variations
o 3partition
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
pencilandpaper games
o Chess, Go, Othello, and other board games
·
Inapproximability
o PCP theorem and OPTpreserving reductions
o APXhardness (e.g., Vertex Cover)
o Setcover hardness
o Group Steiner tree
o kdense subgraph
o Label cover hardness
o Unique Games Conjecture (UGC)
o Independent set
·
Fixedparameter
intractability
o Parameterpreserving reductions
o W hierarchy
o Cliquehardness and ETH hardness
o Kernelization hardness
·
3SUMhardness
(n^{2} and the Exponential Time Hypothesis)
·
Allpair
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
NPcompleteness proofs: reductions from 3Partition
Scanned handwritten notes
Scribe notes by students
Cubic hardness and allpair shortest paths
Scanned handwritten notes
Scribe notes by students
Quadratic hardness and 3SUM
Scanned handwritten notes
Scribe notes by students
3SAT and NPhardness proofs
Scanned handwritten notes
Scribe notes by students
Further NPhardness and ways to cope with
NPhardness
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)
Approximationpreserving and gappreserving
reductions, PCP theorems
Scanned handwritten notes
(combined notes)
Scribe notes by students
More examples of approximationpreserving and
gappreserving reductions
Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
APXhardness proofs via gappreserving reductions
Scanned handwritten notes
(combined notes)
Scribe notes by students
Gap amplification, integrality gap, and uniquegame
conjecture Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
Introduction to fixedparameter 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)
Whardness 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
PPADcompleteness
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 





















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 NPCompleteness: book by Michael R. Garey and David S.
Johnson
2. Johnson's followup NPcompleteness
Columns
3. Games,
Puzzles, & Computation: book by Robert A. Hearn and Erik D. Demaine
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 email 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:


Lectures: 
TuTh 3:30pm4:45pm 
Location: 
CSI 3118 
Office hours: 
By appointment via email 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 

