Steam-powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 533: Complexity Lower Bounds: Communication Complexity and Beyond
  CSE Home  About Us    Search    Contact Info 

Administrative
 Syllabus
Lecture Notes
 Lectures 1 & 2
 Lectures 3 & 4
 Lectures 5 & 6
 Lecture 7
 Lectures 13 & 14
   
Time: TTh 12:00-1:20
Place: Savery 132
Instructor: Paul Beame, beame@cs, Sieg 416, 543-5114
Text: Kushilevitz and Nisan Communication Complexity  Cambridge University Press

In computational complexity we study how much time or space (or whatever other limited resource) we need to use to solve computational problems. Of course it would be great if we could always solve them using very little of these resources! (Although computer science might be a whole lot more boring if we could.) In reality, we find ourselves coming up against apparent limits to what we can do with limited resources. Are we just not smart enough? Research in complexity lower bounds aims to show that it isn't just our stupidity -- we can actually prove limiting lower bounds on the resources needed by ANY computer (no matter how intelligently programmed) to solve specific computational problems.

This course will begin with completely elementary material and build up to some of the latest and hottest research in complexity lower bounds. We will start with commmunication complexity, a very simple way to look at complexity, which was originally devised as an abstraction to simplify and generalize lower bounds for VLSI layout of circuits. Although communication complexity is quite simple, it has had many surprising applications in the rest of computational complexity and we will cover many of them. We also visit several other gems in complexity lower bounds as time permits.

Email Log: (All mail sent to cse533@cs. Last: [an error occurred while processing this directive].)

Instructions for Preparing Lecture Notes


CSE logo Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to beame]