DIKU Bits: You Can't Do That

Portrait of Srikanth

Speaker

Srikanth Srinivasan, Associate Professor in the Algorithms and Complexity (AC) section

Title

You Can't Do That

Abstract

As computer scientists, we typically care about efficient algorithms for various computational problems. But some of us have a rather different (one might even say opposite) goal: to show that certain computational problems are irredeemably difficult. Why might we want to do that? And how could we hope to do it? This talk will be a gentle introduction to the topic of such "no-go theorems" and the new mathematical questions that it raises, many of which are quite simple to state but as yet unresolved.

(The title has been shamelessly stolen from the name of a course about similar topics at Dartmouth college.)

Which courses do you teach?

Computability and Complexity (CoCo), Approximation algorithms (APX) and Randomized algorithms (RA)

Which technology/research/projects/startup are you excited to see the evolution of?

Anything related to quantum computing.