# Algorithmic Lower Bound Techniques

## Seminar

## Basic Information

Given by: | Parinya Chalermsook (and featured a guest lecture by Mayank Goswami) |
---|---|

Time: | Thursday, 14:00- 16:00 |

Room: | 023 |

First Meeting: | October 29th. |

Credits: | 7 credit points |

Grade formula: | 30% scribe + 30% final report + 40% final presentation |

Prerequisites: | You will need to be mathematically mature. You should be able to read and understand technical/mathematical papers on your own. The background lectures also assume basic knowledge in Algorithms and Data Structures but nothing else. |

## News

- [Nov 6] Lectures 3 & 4 are rescheduled. Please see the table below.
- [Oct 30] Important: Please send me an e-mail if you want to take this course for credits.

## Description

Algorithms are ubiquitous in all areas of computer science research. Unfortunately, sometimes due to inherent limits of computations (or computational models), we are unable to design efficient algorithms for our problems, e.g., we cannot achieve an efficient approximation algorithm that is 10% close to the optimal, or an exact algorithm that is both space and time efficient.

In this seminar, we will learn various techniques to prove that a problem is computationally hard. Lower bound techniques are very useful as a toolkit for algorithm designers. They not only tell us when we need to turn to different problem formulations/models, but looking at a problem from the perspectives of algorithms and lower bounds simultaneously helps us understand better the inherent features that make the problem easy or hard.

## Content

This seminar has 2 components. In the first component, I will give 6-7 background lectures on lower bounds. We will cover (tentatively):

- Lower bounds for exact algorithms (2 lectures): For instance, we will prove that solving a particular problem requires running time at least 2n or nc for some c, assuming some plausible complexity assumptions.
- Inapproximability (2 lectures): We will prove that a polynomial time algorithm cannot achieve a certain approximation factor assuming P!=NP. In this part, I will cover Feige's log n hardness for approximating Set Cover and Hastad 3-bit PCPs (which implies tight hardness for approximating 3SAT).
- Communication lower bounds (2 lectures): We will cover lower bound techniques based on communication complexity. We will prove a couple of streaming and data structure lower bounds.

Scribe note: The first component will end in mid December. In this component, you are required to write a scribe note that summarizes one of the lectures. The scribe is due 4 weeks after the lecture is over.

The second component is the class project. Each participant is required to pick a paper, read, summarize, and present it. Instead of choosing papers based on the instructor's interests, students can feel free to choose it based on their own interest :) Of course, I could give you some pointers on this, but the ideal choice would be a paper that is directly related to the lower bound side of your research interest.

Final presentation: The 30-minute final presentation will be done in February. The goal of such presentation is NOT to present a complete proof but rather the *key ideas* that should be highlighted.

Final report: The final paper is due 2 weeks after your presentation. It is expected to be about 5 - 10 pages long.

## Schedule

Date | Speaker | Topic | Reference |
---|---|---|---|

Oct 29 | Parinya | Introduction to the seminar. Running time lower bounds for exact algorithms and size parameter of reductions. | [note] |

Nov 5 | Parinya | Inapproximability and gap parameters; PCP theorem; boosting the gap via graph products. | |

Nov 9* 4pm | Parinya | Randomized graph products and free-bit PCP; Label Cover; | |

Nov 24* 4pm | Parinya | Dictatorship test and hardness of 3LIN. | |

Dec 10 | Parinya | Communication complexity | |

Dec 17 | Parinya | Randomized CC & Lower bounds for Frequency Moments | |

| End of the lectures | ||

Feb 4 | Pavel | Streaming lower bounds | |

Feb 11 | Thorsten | Subcubic equivalences between paths, matrix, and triangles. | |

Feb 18 | ** | ** cancelled ** | |

Feb 25 | Gorav | Property testing & Communication complexity | |

Mar 3 | Daniel | Introduction to data structure lower bounds | |

Mar 10 | Davis | Feige's random 3SAT hypothesis | |

Mar 17 | Andreas | TBD | |

Mar 24 | Aditi |