Time-space hardness of learning sparse parities

DOI10.1145/3055399.3055430MaRDI QIDQ4978047zbMATH OpenOpenAlexFDO

Authors 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

lower boundsFourier analysisbranching programPAC learningtime-space tradeoffbounded storage cryptography

Mathematics Subject Classification ID

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

Recommendations

• Fast learning requires good memory: a time-space lower bound for parity learning
• On the hardness of sparsely learning parity with noise
• On noise-tolerant learning of sparse parities and related problems
• An improved algorithm for learning sparse parities in the presence of noise
• On the hardness of learning sparse parities

Cited in

(17)

• On bounded storage key agreement and one-way functions
• Extractor-based time-space lower bounds for learning
• Speak much, remember little: cryptography in the bounded storage model, revisited
• Two Party Distribution Testing: Communication and Security
• Time-space lower bounds for two-pass learning
• On the hardness of learning sparse parities
• scientific article; zbMATH DE number 7758323 (Why is no real title available?)
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Efficient convex optimization requires superlinear memory
• Secure multiparty computation in the bounded storage model
• Quantum logspace algorithm for powering matrices with bounded norm
• Improved learning of \(k\)-parities
• Fast learning requires good memory: a time-space lower bound for parity learning
• Authentication in the bounded storage model
• Memory-sample lower bounds for LWE
• Memory-sample lower bounds for learning with classical-quantum hybrid memory
• Entropy samplers and strong generic lower bounds for space bounded learning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978047)