|
CSE Home |
About Us |
Search |
Contact Info |
|
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].) |
||||||||||||||||||||||||||||||||||||||||
|
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] | |