Computational Complexity

Computational Complexity

This course is taken by Manindra Agrawal. Half way down the course, he started on the PCP theorems and I thought it would be good to scribe the notes. I shall try to make it as detailed as possible.

Goes without saying, if anyone notices any serious mistakes in my notes, please tell me.

Lecture 1	:	Derandomization: The Deathly Hallows	[PDF]	[TeX]
Lecture 2	:	Expanders: Spectral and Vertex Expansion	[PDF]	[TeX]
Lecture 3	:	Random Walks on Expanders	[PDF]	[TeX]
Lecture 4	:	Constructing Expanders: The Zig-Zag Product	[PDF]	[TeX]
Lecture 5	:	Towards the Proof of PCP Theorem	[PDF]	[TeX]
Lecture 6	:	Gap Amplification	[PDF]	[TeX]

And a single file with all the above lectures together: here.

Computational Complexity

Computational Complexity

Instructor		Dr. Sarah M. Ryan 3014 Black Engineering, 294-4347 smryan@iastate.edu
Office Hours		TR 1:30 - 3:00 p.m.
Time & Place		MWF 12:00 - 12:50 p.m., 1034 Black Please note: Contrary to ISU convention, we will begin at 12:00 promptly, not 12:10.
Text		Network Flows: Theory, Algorithms and Applications,by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, published by Prentice Hall, 1993 This book won the Institute for Operations Research and the Management Sciences (INFORMS) Lanchester Prize for the best contribution to OR/MS published in English in 1993.
Course Web Page		http://www.public.iastate.edu/~smryan/ie510/index.htm Homework assignments and solutions and other material will be made available here as the semester progresses. Check it often!
Description		Many optimization problems can be modeled in terms of flows through networks. A network formulation can provide a clear visual representation of the problem and enable efficient solution methods. In particular, many discrete and nonlinear problems can be solved very efficiently as network flows. Homework exercises will be assigned every 1-2 weeks to be handed in and graded. Students will complete semester projects chosen from their own interests or a suggested list. There will be three exams.

Tentative Topic List

The following sections in Ahuja, Magnanti and Orlin: 1.1-4 Introduction 2.1-5 Paths, Trees and Cycles 3.1-6 Algorithm Design and Analysis 4.1-5 Shortest Paths: Label-Setting Algorithms 5.1-6 Shortest Paths: Label-Correcting Algorithms Chapters 4 and 5 will be supplemented with instructor’s notes on dynamic programming formulation, application and methods. 6.1-6 Maximum Flows: Basic Ideas 7.1-2,6-7 Maximum Flows: Polynomial Algorithms 9.1-7 Minimum Cost Flows: Basic Algorithms 11.1-5, 12 Minimum Cost Flows: Network Simplex Algorithms 12.1-6 Assignments and Matchings 13.1-5 Minimum Spanning Trees 19.7-9 Additional Applications

A "Tutorial on Computational Complexity" by Craig Tovey (2002) is in Interfaces Vol 32, No. 3. (If you follow this link from an ISU computer, you should be logged on to Extenza-INFORMS with full access to articles.)

Class notes:

Introduction

Chapter 1

Chapter 2 Please read section 2.2 before Monday, 8/30/04

Chapter 3

Chapter 4

Chapter 19

Chapter 5

Dynamic Programming Part 1

Dynamic Programming Part 2

Chapters 6 and 7

Chapter 9

Chapter 11

Chapter 12

Chapter 13

Chapter 16