Extractor-based time-space lower bounds for learning

DOI10.1145/3188745.3188962zbMath1428.68238arXiv1708.02639OpenAlexW2962750290MaRDI QIDQ5230356

Avishay Tal, Ran Raz, Sumegha Garg

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1708.02639

zbMATH Keywords

time-space tradeoffbranching programsextractorslearning from samples

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries ⋮ Authentication in the bounded storage model ⋮ Speak much, remember little: cryptography in the bounded storage model, revisited ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ On the Bias of Reed--Muller Codes over Odd Prime Fields ⋮ Unnamed Item ⋮ Time-space lower bounds for two-pass learning ⋮ Two Party Distribution Testing: Communication and Security

This page was built for publication: Extractor-based time-space lower bounds for learning