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

bounded storage cryptographybranching programFourier analysislower boundsPAC learningtime-space tradeoff

Mathematics Subject Classification ID

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

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

(18)

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

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)