Logic is an important field of research with many aspects. In this talk we will discuss in particular the difference between logic as reasoning and logic as a theory about reasoning.

In a graph, we call a vertex well-mixing if the standard random walk starting from that vertex reaches close to its stationary distribution fast (say within 'polylogarithmic in the size of the vertex set' steps).

Since its invention by Robbins and Monro in 1951, the stochastic approximation (SA) algorithm has been a widely used tool for finding solutions of equations, or minimizing functions, with noisy measurements.

The "nearest neighbor (NN) classifier" labels a new data instance by taking a majority vote over the k most similar instances seen in the past. With an appropriate setting of k, it is capable of modeling arbitrary decision rules.

In this talk, we will consider algorithmic problems which follow the following template: given a real-valued multivariate polynomial f(x) of degree d, is it approximately equal to a sum of a few "simple" polynomials, i