Time-space hardness of learning sparse parities

DOI10.1145/3055399.3055430zbMath1370.68132OpenAlexW2626222921MaRDI QIDQ4978047

Gillat Kol, Ran Raz, Avishay Tal

Publication date: 17 August 2017

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

Full work available at URL: https://doi.org/10.1145/3055399.3055430

zbMATH Keywords

Fourier analysislower boundsPAC learningtime-space tradeoffbranching programbounded storage cryptography

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (8)

Secure multiparty computation in the bounded storage model ⋮ Authentication in the bounded storage model ⋮ Unnamed Item ⋮ Speak much, remember little: cryptography in the bounded storage model, revisited ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Unnamed Item ⋮ Time-space lower bounds for two-pass learning ⋮ Two Party Distribution Testing: Communication and Security

This page was built for publication: Time-space hardness of learning sparse parities