Tight Time-Space Lower Bounds for Constant-Pass Learning
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 that followed extended this result to a large class of learning problems. Until recently, all these results considered lear...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2310.08070 http://arxiv.org/abs/2310.08070 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|