CMSC858F: Algorithmic Lower Bounds: Fun with Hardness Proofs,
Fall 2014
Prof. Mohammad T. HajiAghayi
See also the sister course to this course at MIT by Prof. Erik Demaine taught simultaneously.
Latest Announcements
· Exam date: Thursday Nov 20, 2014, 3:30-6,
AVW 3258 (notice the different room)
· The third assignment is released and is due Nov 12 at 5pm.
· Topics of the projects should be checked with the instructor and finalized by Sep 30, 2014
· The second assignment is released and is due Oct 30 at 5pm.
· The first assignment is released and is due Thu, Oct 2, at 4pm.
· See the poster prepared by Erik Demaine for the sister course.
·
See the course agenda
· First lecture on September 2, 2014 at CSI 2118
· Templates .tex .sty to scribe
Assignments
·
Homework 3 due TBD in my mailbox of the first floor
of A.V. Williams.
·
Homework 2 due Oct 23 in my mailbox of the first
floor of A.V. Williams.
·
Homework 1 due Oct 4 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 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):
09/02/2014: Review of course
description, motivation for the course and its topics
Scanned handwritten notes
Scribe notes by students
09/04/2014: Introduction and review of
complexity theory: P, NP, EXP, PSPACE
Scanned handwritten notes
Scribe notes by students
09/09/2014: NP-completeness proofs:
reductions from 3-Partition
Scanned handwritten notes
Scribe notes by students
09/11/2014: Cubic hardness and all-pair
shortest paths
Scanned handwritten notes
Scribe notes by students
09/16/2014: Quadratic hardness and 3-SUM
Scanned handwritten notes
Scribe notes by students
09/18/2014: Wrap up of previous two
topics on all-pair shortest paths and 3-SUM
Scanned handwritten notes (see previous two
sessions)
Scribe notes by
students (see previous two
sessions)
09/23/2014: 3-SAT and NP-hardness proofs
Scanned handwritten notes
Scribe notes by students
09/25/2014: 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)
09/30/2014: Different levels of inapproximability for minimizing problems
Scanned handwritten notes
(combined notes)
Scribe notes by students
10/02/2014: Different levels of inapproximability for maximizing problems
Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
10/07/2014: Approximation-preserving and
gap-preserving reductions, PCP theorems
Scanned handwritten notes
(combined notes)
Scribe notes by students
10/09/2014: 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)
10/14/2014: APX-hardness proofs via
gap-preserving reductions
Scanned handwritten notes
(combined notes)
Scribe notes by students
10/16/2014: Gap amplification,
integrality gap, and unique-game conjecture Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
10/21/2014: Introduction to
fixed-parameter tractability
Scanned handwritten notes
(combined notes)
Scribe notes by students
10/23/2014: Parameterized reductions
and assumptions
Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
10/28/2014: W-hardness hierarchy and
weighted circuit satisfiability
Scanned handwritten notes
(combined notes)
Scribe notes by students
10/30/2014: 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)
11/04/2014: Introduction to online
algorithms and lower bounds for paging
Scanned handwritten notes
(combined notes)
Scribe notes by students
11/06/2014: 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)
11/11/2014: Introduction to streaming algorithms:
INDEX and DISJOINTNESS tools for lower bounds
Scanned handwritten notes
(combined notes)
Scribe notes by students
11/13/2014: Several examples of
streaming algorithm lower bounds
Scanned handwritten notes
(combined notes)
Scribe notes by students (combined scribe notes with the previous session)
11/20/2014: Exam Day
11/20/2014: Thanksgiving Day
12/02/2014: Algorithmic game theory
lower bounds and PPAD-completeness
Scanned handwritten notes
Scribe notes by students
12/04/2014: Paper and Project presentation
12/09/2014: Paper and Project presentation
12/11/2014: Paper and Project presentation see below (last
day of the class)
Written papers are due
List of
projects
|
Title |
Members |
Slides |
Scribes |
|
Hardness of Facility Location Problems |
Karthik Abinav S, Thomas Pensyl |
||
|
On complexity of Slide-and-Merge Games |
Ahmed Abdelkader, Aditya Acharya,
Philip Dasler |
||
|
Computability and Convergence of Market Equilibria |
Manish Purohit, Anshul
Sawant |
||
|
Hardness of Modern Allocation Problems |
Melika Abbolhassani, Hossein Esfandiari |
||
|
Online Network Design |
Sina Dehghani, Soheil Ehsani, Saeed Seddighin |
||
|
Round Complexity |
Huijing Gong |
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
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:
|
|
|
Lectures: |
TuTh 3:30pm-4:45pm |
|
Location: |
CSI 2118 |
|
Office hours: |
By appointment via e-mail OR the hour immediately
following class. |
|
Office: |
A.V. Williams Bldg., Room 3249 |
|
Phone: |
301-405-2741 |
|
Email: |
The first 8 letters of instructor’s last name
(AT) cs (DOT) umd
(DOT) edu |
|
|
|