# Complexity Theory of Polynomial-Time Problems

## Advanced Course, 2+1

Lectures: | Thursday, 16:15 - 18:00, E1.4 024 |

Lecturers: | Karl Bringmann and Sebastian Krinninger |

First lecture: | 21 April 2016 |

Tutorials: | Friday, 12:15 - 14:00, U12 E1.1, biweekly |

Assistant: | Gorav Jindal |

First tutorial: | 13 May 2016 |

Credits: | 5 |

Prerequisites: | No formal requirements, but basic knowledge in algorithms & data structures and complexity theory is assumed. |

## News

- The oral exam will take place in September. Please mark possible dates in the following doodle, till August 15 at the latest: http://doodle.com/poll/v9bktxdrktv5w98e

## Description

Complexity theory traditionally distinguishes whether a problem can be solved in polynomial-time (by providing an efficient algorithm) or the problem is NP-hard (by providing a reduction). For practical purposes however the label "polynomial-time" is too coarse: it may make a huge difference whether an algorithm runs in say linear, quadratic, or cubic time. In this course we explore an emerging subfield at the intersection of complexity theory and algorithm design which aims at a more fine-grained view of the complexity of polynomial-time problems. We present a mix of upper and lower bounds for fundamental poynomial-time solvable problems, often by drawing interesting connections between seemingly unrelated problems. A prototypical result presented in this course is the following: if there is a substantially faster algorithm for computing all-pairs shortest paths in a weighted graph, then there also is a substantially faster algorithm for checking wether the graphs has a negative triangle (and vice versa). The techniques for proving such statements have been developed quite recently and most results taught in this course are less than three years old.

An important part of the course are the exercises, where you will design conditional lower bounds essentially on your own. There will be 6 exercise sheets and you need to collect at least 50% of all points on exercise sheets to be admitted to the exam.You are allowed to collaborate on the exercise sheets, but you have to write downa solution on your own, using your own words.Please indicate the names of your collaborators for each exercise you solve.Further, cite all external sources that you use (books, websites, research papers, etc.).

## Slides

- Lecture 01 - Introduction
- Lecture 02 - SETH and OV
- Lecture 03 - Polynomial Method for OV
- Lecture 04 - Polynomial Method for APSP
- Lecture 05 - Subcubic Equivalences
- Lecture 06 - 3SUM Algorithms
- Lecture 07 - 3SUM Hardness
- Lecture 08 - Boolean Matrix Multiplication
- Lecture 09 - Dynamic Algorithms Upper Bounds
- Lecture 10 - Dynamic Algorithms Lower Bounds
- Lecture 11 - Nondeterministic SETH
- Lecture 12 - More on OMv
- Lecture 13 - Recap, Further Directions, Open Problems

## Further Reading

Lecture 01: [Roditty,Vassilevska-Williams'13]

Lecture 02: [Impagliazzo,Paturi,Zane'01], [Bringmann'14], [Bringmann,Künnemann'15], [Abboud,Backurs,Vassilevska-Williams'15]

Lecture 03: [Abboud,Williams,Hu'14]

Lecture 04: [Williams'14]

Lecture 05: [Vassilevska-Williams,Williams'10], [Abboud,Grandoni,Vassilevska-Williams'15], [Backurs,Dikkala,Tzamos'16]

Lecture 06: [Gronlund,Pettie'14], [Gajentaan,Overmars'95]

Lecture 07: [Patrascu'10], [Kopelowitz,Pettie,Porat'16], [Baran,Demaine,Patrascu'05]

Lecture 08: [Bläser'13], [Clifford,Indyk,Porat'09], [Czumaj,Lingas'07]

Lecture 09: [King'99], [Baswana et al.'02]

Lecture 10: [Abboud,Vassilevska-Williams'14], [Henzinger et al.'15]

Lecture 11: [Carmosino,Gao,Impagliazzo,Mikhailin,Paturi,Schneider'15], [Williams'16]

Lecture 12: [Larsen,Williams'16]

## Tentative Schedule

Lecture | Tutorial | Teacher | Topic |

21 Apr | KB+SK | Introduction | |

28 Apr | KB | Lower bounds from SETH and Orthogonal Vectors (→Ex. sheet 1) | |

05 May | No lecture | ||

12 May | SK | The polynomial method I: Orthogonal Vectors | |

13 May | GJ | Tutorial 1 | |

19 May | SK | The polynomial method II: All-Pairs Shortest Paths (→Ex. sheet 2) | |

26 May | No lecture | ||

02 Jun | KB | Subcubic equivalences between path, matrix, and triangle problems (→Ex. sheet 3) | |

03 Jun | GJ | Tutorial 2 | |

09 Jun | KB | 3SUM Hardness I | |

16 Jun | SK | 3SUM Hardness II (→Ex. sheet 4) | |

17 Jun | GJ | Tutorial 3 | |

23 Jun | KB | Boolean Matrix Multiplication: Upper bounds and hardness results (→Ex. sheet 5) | |

30 Jun | SK | Dynamic graph algorithms I: Upper bounds | |

01 Jul | GJ | Tutorial 4 | |

07 Jul | SK | Dynamic graph algorithms II: Lower bounds (→Ex. sheet 6) | |

08 Jul | GJ | Tutorial 5 | |

14 Jul | KB | Nondeterministic SETH | |

21 Jul | SK | More on OMv | |

22 Jul | GJ | Tutorial 6 | |

28 Jul | KB | Recap, Further Directions, Open Problems | |

29 Jul | GJ | Q&A session |