Computational Complexity

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and E/poly.

We show the following:

1. (Unconditional Lower Bounds ...

Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data ...${\mathbb{}}^{}$${}_{}\mathrm{}\mathrm{}\mathrm{}$${}_{}{}^{\mathrm{}}$$\mathrm{}$$$