Computer science colloquia: Pavan Aduri
| Date/Time: | Thursday, 02 Feb 2012 at 3:40 pm |
|---|---|
| Location: | B29 Atanasoff |
| Cost: | Free |
| Phone: | 515-294-6516 |
| Channel: | College of Liberal Arts and Sciences |
| Categories: | Lectures |
| Actions: | Download iCal/vCal | Email Reminder |
Several problems in complexity theory can be formulated as graph theoretic problems. Resolving these graph theoretic problems lead to some fundamental results in complexity theory. In this talk, we highlight some graph theoretic problems such as pebbling, ruling sets and unique shortest paths, and mention their relationships to complexity theory. We discuss some known results and open problems.
No background in complexity theory is assumed.