Quantum Meta-Complexity for Cryptography, Verification, Learning, and More(?)

Abstract

This talk will give a high level survey of the role that meta-complexity has played in connecting diverse areas of theoretical computer science, with a focus on the quantum setting. Meta-complexity–the study of computational problems that are concerned with the complexity of other problems–has proven to be a remarkable tool for characterizing the randomness vs simplicity of objects, providing tools in areas as diverse as protein folding, machine learning, and non-constructive proofs. In recent years it has been used as a tool that has so far connected deep questions in both classical and quantum cryptography, learning, and verification. I will discuss these connections and the frontiers for future work.

Biography

Matthew Gray is an associate professor of computer science here at SFSU researching quantum cryptography and complexity theory. He was born in Berkeley California, studied CS and mathematics at UC Santa Cruz, worked for Microsoft Norway, taught at Renton Technical College outside of Seattle, and just finished his PhD at the University of Oxford. His core research seeks to understand how the limits of feasible computation are changed by the introduction of quantum computing using the tool kit of meta-complexity, the study of computational problems concerned with the complexity of other problems.