Algorithmic Lower Bound Techniques

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 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.