Tight Time-Space Lower Bounds for Constant-Pass Learning

Xin Lyu, Avishay Tal, Hongxun Wu +1

In his breakthrough paper, Raz showed that any parity learning algorithm requires either quadratic memory or an exponential number of samples [FOCS'16, JACM'19]. A line of work tha…