Algorithmic Magic: Behind the Scenes of Modern Computer Science

Computer science permeates many aspects of our lives, from games on a smartphone to global online banking systems. It is crucial for scientists and programmers within the field to have a theoretical and robust understanding of its limits.

On Wednesday, January 20, at 8 p.m. in Beckman Auditorium, Professor of Computer Science Chris Umans will discuss how computer scientists identify and conceptualize computational problems, what sorts of ideas are used to solve them, and how they encapsulate deep questions about the nature of computation itself. Admission is free.

What do you do?

I am a theoretical computer scientist in the Division of Engineering and Applied Science, which means I am interested in understanding the possibilities and limitations of computation, in a provable, mathematical sense. Computational complexity attempts to answer the question, what is computationally feasible given limited computational resources? It studies general techniques for trading off resources such as running time, storage space, randomness, and parallelism; it devises methods for transforming whole classes of problems into simple "complete" problems that capture the difficulty of the whole class; and it establishes results about the limits of efficient computation, in a rigorous way. It encompasses some of the deepest and most fundamental open—or unsolved—problems in computer science and mathematics.

Computational complexity also excels at exposing computational problems that we regard as "fundamental" because they lie at the heart of many applications.

I also work on a variety of problems concerning the power of randomness in computation, algorithms for some fundamental algebraic problems, and some questions in quantum computation. Much of my work has an algebraic component to it.

Why is this important?

Theoretical computer science is the "science" behind computer science. It develops the ideas and the mathematics to be able to solve key problems in fast and clever ways and these problems in turn lie at the heart of the technologies that permeate our everyday lives.

Understanding what's possible algorithmically and what's computationally impossible is a fundamental scientific and mathematical question. One major implication is for computer security. We base cryptography and online security on the believed difficulty of problems which seem intractable—problems that can theoretically be solved but not in practice—but we don't know how to prove that these problems don't have an unexpected, fast solution. If we're wrong about their assumed intractability, most of the cryptography currently in use can be broken.

How did you get into this line of work?

As a kid, I enjoyed programming and mathematics. When I took my first course on algorithms I realized I enjoyed figuring out clever ways to solve problems more than coding the solutions themselves. When I learned about the P versus NP problem and the other deep unsolved problems of computational complexity, I was hooked. I feel very fortunate to have the freedom to think deeply about the difficult problems that fascinate me.