Algorithmic Lower Bound Techniques


Basic Information

Given by:Parinya Chalermsook (and featured a guest lecture by Mayank Goswami
Time:Thursday, 14:00- 16:00 
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.  


  1. [Nov 6] Lectures 3 & 4 are rescheduled. Please see the table below. 

  2. [Oct 30] Important: Please send me an e-mail if you want to take this course for credits. 


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. 



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 2or n 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. 


Oct 29Parinya

Introduction to the seminar. Running time lower bounds for exact algorithms and size parameter of reductions. 

Nov 5ParinyaInapproximability and gap parameters; PCP theorem; boosting the gap via graph products. 
Nov 9*  
ParinyaRandomized graph products and free-bit PCP; Label Cover; 
Nov 24*     4pmParinyaDictatorship test and hardness of 3LIN. 
Dec 10ParinyaCommunication complexity 
Dec 17ParinyaRandomized CC & Lower bounds for Frequency Moments 


End of the lectures
Feb 4PavelStreaming lower bounds
Feb 11ThorstenSubcubic equivalences between paths, matrix, and triangles. 
Feb 18**** cancelled **  
Feb 25GoravProperty testing & Communication complexity 
Mar 3DanielIntroduction to data structure lower bounds
Mar 10DavisFeige's random 3SAT hypothesis
Mar 17AndreasTBD
Mar 24Aditi