The code intersection problem, first introduced by the breakthrough work of Yamakawa and Zhandry, is the problem of finding a point in the intersection of the image of a linear error correcting code and the pre-image of a product hash function.  While it was first introduced as a way to demonstrate quantum advantage without structure, it has proven to be an extremely versatile and powerful idea for understanding a host of problems in quantum cryptography, complexity, and algorithms.

In this talk, I will give an overview of the code intersection problem and the Yamakawa-Zhandry algorithm, and present an application of the problem to quantum complexity, namely the problem of separating quantum versus classical proofs and advice.  Along the way, I will try to highlight some of the common modifications and tricks that have allowed the code intersection problem to extend its reach beyond its original application.  Despite much progress, the code intersection problem is still very mysterious and fascinating to me, and I will spend some time talking about my favorite open questions related to it.  

Based on joint work with Andrew Huang and Vinod Vaikuntanathan

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*