Probability Seminars

## Learning low-degree functions from few random queries

### With Alexandros Eskenazis (Cambridge)

# Learning low-degree functions from few random queries

Let f be an unknown function on the n-dimensional discrete hypercube. How many values of f do we need in order to approximately reconstruct the function? In this talk we shall discuss the random query model for this fundamental problem from computational learning theory. We will explain a newly discovered connection with a family of polynomial inequalities going back to Littlewood (1930) which will in turn allow us to derive sharper estimates for the query complexity of this model, exponentially improving those which follow from the classical Low-Degree Algorithm of Linial, Mansour and Nisan (1989). Based on joint work with Paata Ivanisvili (UC Irvine).

- Speaker: Alexandros Eskenazis (Cambridge)
- Tuesday 02 November 2021, 15:30–16:30
- Venue: MR12 Centre for Mathematical Sciences.
- Series: Probability; organiser: Perla Sousi.