Inference Dimension

John Iacono, New York University and Université Libre de Bruxelles

November 7, 2017

Daniel M. Kane, Shachar Lovett, Shay Moran recently introduced the concept of inference dimension [arXiv:1704.03564], which they then used to show significantly faster nonuniform algorithms for a variety of problems [arXiv:1705.01720]. In this talk I will go over the definitions of inference dimension, the applications, and a discussion of possible extensions and open problems.