Sasha Golovnev is an associate professor of computer science in the Cornell Ann S. Bowers College of Computing and Information Science. His research interests include computational complexity, algorithms, pseudorandomness, learning theory, and cryptography.
Before joining Cornell, Golovnev was an assistant professor of computer science at Georgetown University, a research scientist at Columbia University and Yahoo Research, and a Rabin Postdoctoral Fellow at Harvard University. He received his Ph.D. in computer science from New York University in 2017.
What is your academic focus?
My academic focus is theoretical computer science, with a particular emphasis on computational complexity.
Could you briefly summarize your research?
My group's research is driven by the question: what computational resources are required to solve a given computational problem? Here, “resources” may refer to various measures, including time, space, communication, randomness, and data. We are particularly interested in drawing connections between these resources and the different areas of theoretical computer science that study them.
What inspired you to pursue a career in this field?
I believe that the questions in computational complexity are among the most fundamental ones we can ask. Their beauty becomes especially apparent when you see the many deep connections they have to different areas of mathematics. Once you’ve experienced that, it’s hard to imagine pursuing a career in any other field :)
What scientific questions are you looking to answer or areas you plan to explore?
I am particularly excited about some of the longstanding questions at the heart of circuit complexity. I believe that, after decades of progress, we may finally have enough understanding to resolve questions first raised by Leslie Valiant about the superlinear complexity of Boolean functions, as well as the closely related question of matrix rigidity. I would be excited to see resolutions to these problems in the near future.
Why Cornell?
Cornell has an incredible history in theoretical computer science, from the pioneering work of Juris Hartmanis and John Hopcroft to the researchers working at the cutting edge of the field today. I’m excited about working with both the faculty and students at Cornell.