Here's a function with circuit complexity roughly 2k gates at depth 10: xor of 1000 input bits. So, allowing for a little wiggle room... does this theorem imply that a stack of 10's of MLPs of width in the 1000's can learn a 1000-bit xor function?
[posted this in parallel with Kaarel's answer below] This is Bayesian learning, and here the answer is yes. Kaarel actually has a really cool construction of depth 2 that can do xor of 1000 bits.
Of course SGD can't learn (a subset-level) xor by standard learning results. However there are no impossibility results on SGD-learning a version of xor "with advice", where the target is a concatenation of all xors over a binary tree (so for 4 bits, this is the 3-dimensional output (xor(x1, x2), xor(x3, x4), xor(x1, x2, x3, x4)). Here lazy/ kernel methods still provably require exponential time or exponential sample complexity but empirical methods just work.
This is a regime where a dynamical version of our mean field results suggests that in infinite width mean field settings, things should stabilize in width if one chooses lr carefully (essentially in a Greg Yang sense). This does seem to happen, though the width stabilization is slow. In particular I am working with a collaborator/MARS mentee, Sergey, on trying to analyze the SGD/Adam results of various deep ladder xor networks (currently up through 16 bit parity) via mean field-esque methods. The weird result Sergey sees is that for 8-bit parity, there's some learning of the corresponding feature already at the first layer whereas for 16-bit parity the model definitively first learns the 4- and 8-bit xors at early layers and then combines them into 16-bit xor
Here are the slides of a talk Kaarel gave, presenting work with Dmitry establishing that (even arbitrarily overparametrized) neural net bayesian learning has a circuit prior — and thus, when learning a function which is implemented by some small circuit, only requires a small amount of training data to get good test accuracy — for certain scalings of the prior and with various other important caveats. The slides offer a self-contained presentation of the simplest version of the result. See the end of the presentation (slides 36–37) for a bunch of open problems in NN learning theory.