Abstract
This two-lecture tutorial will survey the complexity-theoretic foundations of quantum supremacy experiments. Topics will include: counting complexity, interference and #P vs Gap-P; worst-case exact sampling hardness results; average-case approximate sampling arguments and their recent extension to quantum random circuit sampling; Google's supremacy experiment and its verification; and alternative arguments for the hardness of these experiments.