|
Event Title: |
"Two applications of Topology to Impossibility results in Computer Science" |
|
Speaker: |
Dr. Amit Chakrabarti |
|
Affiliation: |
Dartmouth College |
|
Abstract/Brief Description: |
Impossibility results have fascinated mathematicians since ancient times, when the Greeks puzzled about trisecting angles and squaring the circle. Today, impossibility results are at the core of theoretical computer science, where they help us understand the fundamental capabilities and inabilities of computation. As with trisection, or squaring the circle, a proof of impossibility typically draws upon mathematics far more advanced than that the required to state the problem. The situation is no different in computer science and in this talk I shall illustrate how two topological results have unexpected applications in the seemingly unrelated field of computer algorithms. The first application is a now-classic result of Ben-or on the element distinctness problem and will introduce decision trees. These in turn play a role in the second application, on testing graph properties, and features some recent work of mine. |
|
Subject Area: |
Mathematics |
|
Date: |
|
|
Time: |
|
|
Venue: |
Lecture Hall - I, Dept. of Mathematics, IISc. |