We consider $L_2$-approximation of functions using linear algorithms and want to compare the power of function values with the power of arbitrary linear information. Under mild assumptions on the class of functions, we show that the minimal worst-case errors based on function values decay at almost the same rate as those with arbitrary info, if the latter decay fast enough. Our results are to some extent best possible and, in special cases, improve upon well-studied point constructions, like sparse grids, which were previously assumed to be optimal. The proof is based on deep results on large random matrices, including the recent solution of the Kadison-Singer problem, and reveals that (classical) least-squares methods might be surprisingly powerful in a general setting.

We are motivated by an interesting problem studied more than 50 years ago by Veech and which can be considered a parity, or mod 2, version of the classical equidistribution problem concerning the irrational rotation sequence. The Veech discrete 2-circle problem can also be visualized as a continuous flat dynamical system, in the form of 1-direction geodesic flow on a surface obtained by modifying the surface comprising two side-by-side unit squares by the inclusion of barriers and gates on the vertical edges, with appropriate modification of the edge identifications. A famous result of Gutkin and Veech says that 1-direction geodesic flow on any flat finite polysquare translation surface exhibits optimal behavior, in the form of an elegant uniform-periodic dichotomy. Here the modified surface in question is no longer such a surface, and there are vastly different outcomes depending on the values of certain parameters.