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 a final year PhD student at the University of Oxford studying quantum
cryptography and complexity theory. He was born in Berkeley California, studied CS and
mathematics at UC Santa Cruz, worked for Microsoft Norway, and taught at Renton
Technical College outside of Seattle, before pursuing his PhD. 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.